tło

Incydent jest dość nietypowym językiem programowania, ponieważ jego lista tokenów nie jest z góry określona, ​​ale raczej wywodzi się z danych wejściowych. Dlatego tokenizacja programu Incydent może być dość trudna, szczególnie jeśli chcesz to zrobić skutecznie. To zadanie polega na robieniu tego samemu.

Zadanie

Twój program otrzyma ciąg wejściowy. Oto algorytm wykorzystywany przez Incydent do tokenizacji:

1. Zidentyfikuj wszystkie ciągi, które występują jako podciąg danych wejściowych na dokładnie trzy sposoby (tj. Są dokładnie trzy wystąpienia tego ciągu w danych wejściowych).
2. Odrzucić każdy z tych łańcuchów, które są podłańcuchem innego takiego napisu (np dla wejścia ababab, jedyne ciąg byłoby ab, nie abądź b, bo ai bto zarówno podrzędnymi ab).
3. Odrzuć wszystkie ciągi, które nakładają się na dane wejściowe. (Na przykład aaaazawiera dokładnie trzy kopie aa, ale kopie te nakładają się na drugi i trzeci znak, więc zostałyby odrzucone. Podobnie, w abababa, są trzy kopie abi trzy kopie ba, ale każda z drugiej do szóstej litery jest na nachodzenie abi ba, tak jak abi babyłyby usunięte).
4. Wszelkie ciągi, które pozostaną w tym momencie, są tokenami używanymi przez program. Tokenizuj oryginalne dane wejściowe w sekwencji tych żetonów (ze względu na odrzucenie w poprzednim kroku będzie tylko jeden sposób, aby to zrobić). Wszelkie znaki na wejściu, które nie są częścią żadnego tokena, są traktowane jako komentarze i odrzucane.

Twój program musi pobrać ciąg jako dane wejściowe i zwrócić odpowiednią tokenizację ciągu (listę tokenów, z których każdy jest wyrażony jako ciąg) jako wynik. Ponadto należy to zrobić co najmniej umiarkowanie skutecznie; w szczególności program musi działać w czasie kwadratowym („O (n²)”) lub lepszym. (Nawiasem mówiąc, prawie na pewno można przejść szybciej niż kwadratowe, ale nie jest to najszybszy algorytm , więc możesz użyć najkrótszego algorytmu, jaki można znaleźć, który mieści się w granicach złożoności.)

Wyjaśnienia

• Chociaż programy incydentów mogą teoretycznie zawierać dowolny z 256 oktetów, dla celów tego wyzwania dopuszczalne jest, aby Twój program obsługiwał tylko dane wejściowe utworzone z drukowalnego ASCII (w tym spacji) oraz znak nowej linii i tabulator. (Wszystkie znane programy incydentów ograniczają się do tego podzbioru). Zauważ, że spacja / nowa linia / tab nie są wyjątkowe i mogą pojawiać się pośrodku tokenów; Incydent traktuje wszystkie 256 oktetów jako nieprzejrzyste.
• Definicja „czasu kwadratowego” brzmi „jeśli rozmiar wejścia zostanie podwojony, program będzie działał wolniej o nie więcej niż stałą plus współczynnik 4”, tj. Jeśli t ( x ) to maksymalny czas, jaki zajmuje Twój program przetworzyć dane wejściowe o rozmiarze x , wtedy musi być pewna stała k, taka, że t (2  x ) <4  t ( x ) + k dla wszystkich x . Pamiętaj, że porównywanie łańcuchów zajmuje czas proporcjonalny do długości łańcuchów.
• Twój program powinien teoretycznie być w stanie obsłużyć programy wejściowe dowolnej długości, jeśli jest uruchamiany w (prawdopodobnie hipotetycznym) wariancie języka, który ma nieograniczoną pamięć i używa nieograniczonych liczb całkowitych (jest OK, jeśli program nie osiągnie tego celu, gdy jest uruchomiony w praktyce z powodu liczby całkowite języka lub pamięć są w rzeczywistości skończone duże). Możesz założyć (w celu obliczenia złożoności), że liczby całkowite, które nie są większe niż długość danych wejściowych, mogą być porównywane w stałym czasie (chociaż pamiętaj, że jeśli użyjesz większych wartości, np. Ze względu na konwersję danych wejściowych na pojedynczej liczby całkowitej, porównanie zajmie dużo czasu proporcjonalnie do liczby cyfr, które mają).
• Możesz użyć dowolnego algorytmu, który mieści się w granicach złożoności, nawet jeśli nie wykonuje on tych samych kroków, co algorytm opublikowany powyżej, pod warunkiem, że daje takie same wyniki.
• Ta łamigłówka dotyczy tokenizacji danych wejściowych, a nie formatowania danych wyjściowych. Jeśli najbardziej naturalny sposób na wyświetlenie listy w twoim języku wymaga niejednoznacznego formatu (np. Rozdzielony znakiem nowej linii, gdy ciągi zawierają dosłowne znaki nowego wiersza lub bez ograniczników między ciągami), nie martw się faktem, że wynik jest niejednoznaczny ( tak długo, jak lista jest faktycznie konstruowana). Możesz chcieć stworzyć drugą wersję swojego zgłoszenia, która generuje jednoznaczne dane wyjściowe, aby pomóc w testowaniu, ale oryginalna wersja jest wersją, która liczy się do oceny.

Przypadek testowy

Dla następującego ciągu wejściowego:

aaabcbcbcdefdfefedghijghighjkllkklmmmmonono-nonppqpq-pqprsrsrstststuvuvu

twój program powinien wygenerować następującą listę wyników:

a a a bc bc bc d e f d f e f e d gh gh gh k l l k k l pq pq pq u u u

Warunek zwycięstwa

Jest to kod-golf , więc wygrywa najkrótszy prawidłowy (tj. Prawidłowe zachowanie wejścia / wyjścia i wystarczająco szybki do wykonania) program, mierzony w bajtach.

C (gcc), 324 bajty

Funkcja fpobiera łańcuch zakończony znakiem null i drukuje tokeny na standardowe wyjście. Wszystkie nowe wiersze można usunąć z kodu poniżej.

f(char*s){
int n=strlen(s),b=0,z[n-~n],F[n+1],u,a,x=0,l,m,*t=z+n;
int K(i){~m&&s[i]^s[a+m]?m=t[m],K(i):++m;}
for(;b<2*n;){
for(a=b++%n,m=l=-1;a+l<n;K(a+l))t[++l]=m;
for(l=0;l<n;++F[m])K(l++),F[l]=z[a]*=b>n?m^z[a]||~(m=t[z[l-m]]):0;
for(printf("%.*s",z[a],s+a);n/b*l&&a+l>x;l--)F[l]^3?F[t[l]]+=F[l]:(a<x?z[u]=0:(z[u=a]=l),x=a+l);
}
}

Ta starsza 376-bajtowa wersja jest nieco łatwiejsza do odczytania; dotyczy to poniższe wyjaśnienie.

*t,m;
char*p;
K(c){for(;~m&&c^p[m];)m=t[m];++m;}
k(i){for(*t=m=-1;p[i];t[++i]=m)K(p[i]);m=0;}
f(char*s){
int n=strlen(s),z[n-~n],F[n+1],u,*Z=z,a=0,x=0,l;
for(t=z+n;a<n;a++){
p=s+a;
for(k(l=z[a]=0);l<n;++F[m])K(s[l++]),F[l]=0;
for(;l&&a+l>x;l--)F[l]^3?F[t[l]]+=F[l]:(a<x?z[u]=0:(z[u=a]=l),x=a+l);
}
for(p=s;*p;printf("%.*s",*Z++,p++))
for(k(x=0);x<n;m==*Z?*Z*=!!z[x-m],m=t[m]:0)
K(s[x++]);
}

k(0)generuje tabelę twzorów pdla algorytmu Knuth – Morris – Pratt. K(c)przetwarza następny znak cciągu wyszukiwania i aktualizacji m, którego długość jest największym prefiksem, pkończącym się na ostatnio przetwarzanym znaku.

W pierwszej forpętli, dla każdego indeksu aw ciągu, liczymy, ile razy każda możliwa wartość mwystępuje podczas wyszukiwania w całym ciągu dla podłańcucha rozpoczynającego się od a. Następnie szukamy największego ltakiego, że lpodciąg długości zaczyna się adokładnie 3 razy. Jeśli jest wystarczająco krótki, aby w całości mógł go zawierać ciąg znaleziony dla poprzedniego a, ignorujemy go. Jeśli się nakłada, usuwamy poprzedni ciąg znaków z ztablicy rejestrującej, które tokeny zostaną zachowane. W przeciwnym razie jego długość jest przechowywana w z.

Następnie ponownie używamy KMP, aby wyszukać ciąg znaków w celu znalezienia tokenów zarejestrowanych w z. Jeśli jeden z nich zostanie znaleziony w miejscu z wpisem 0 z, wiemy, że ten token został usunięty z powodu nakładania się. Jeśli token nie został usunięty, zostanie wydrukowany.

JavaScript, 878 867 842 825 775 752 717 712 704 673 664 650 641 bajtów

Dzięki @Kritixi Lithos za pomoc w
grze w golfa Dzięki @ User2428118 za grę w golfa z 14 bajtów

(Nie działa w IE7) (Newlines należy wpisać jako „ \n” i tabulować jako „ \t” w ciągu wejściowym, wszelkie znaki Unicode należy wprowadzić jako \u####)

w=>{for(a=[],b=[],c=[],d=[],f=[],e=[],k=0;k<(g=w.length);a[k++]=h)for(b[R='push']([]),h=[d[k]=f[k]=j=i=0];i++<g-k;){while(j&&w[k+i]!=w[k+j])j=h[j-1];w[k+i]==w[k+j]&&j++,h[R](j)}for(k=0;k<g;k++)for(j=i=0;i<g;i++)if(w[i]!=w[k+j]){while(j&&w[i]!=w[k+j])j=a[k][j-1];w[i]==w[k+j]?i--:b[k][R](j)}else b[k][R](++j);for(k=0;k<g;c[k++]=l){for(h=f.map(Q=>i=l=0);i<g;)h[b[k][i++]]++;for(;i;)h[i]==3?(l=i,i=0):a[k][--i]?h[a[k][i]]+=h[i+1]:0}for(k=0;g>k++;)for(i=0;(S=c[k])&&i<g;)b[k][i++]==S?d[i-S]=S:0;for(k=0;k<g;k++)for(e[R](w.slice(k,(S=d[k])+k)),i=1;i<S;)f[k+i]=1,f[k]|=S<d[k+i]+i++;f.map((X,i)=>(P=e[i],X?e=e.map(Y=>P==Y?"":Y):0));return e.join``}

Wypróbuj online

Wyjaśnienie, jak to działa i niepoznany kod

Po pierwsze, program generuje tablice Knuth Morris Pratt dla każdego możliwego podciągu;

for(index=0;index<word.length;index++){
  kmpArray=[0];
  j=0;
  for(i=1;i<word.length-index;i++){
    while(j&&word.charAt(index+i)!=word.charAt(index+j)){
      j=kmpArray[j-1];
    }
    if(word.charAt(index+i)==word.charAt(index+j)){
      j++;
    }
    kmpArray.push(j);
  }
  kmpArrays.push(kmpArray);
}

Następnie program wyszukuje maksymalne pasujące długości dla każdego indeksu w słowie z każdym podciągiem. (jest to czas O (n ^ 2))

for(index=0;index<word.length;index++){
  j=0;
  matchLength=[];
  for(i=0;i<word.length;i++){
    if(word.charAt(i)!=word.charAt(index+j)){
      while(j&&word.charAt(i)!=word.charAt(index+j)){
        j=kmpArrays[index][j-1];
      }
      if(word.charAt(i)==word.charAt(index+j)){
        i--;
      }else{
        matchLength.push(j);
      }
    }else{
      j++;
      matchLength.push(j);
      if(j==kmpArrays[index].length){
        j=kmpArrays[index][j-1];
      }
    }
  }
  matchLengths.push(matchLength);
}

Program wykorzystuje te dane, aby znaleźć najdłuższe podciągi, które pojawiają się trzy razy dla każdego początkowego znaku w ciągu.

for(index=0;index<word.length;index++){
  counts=[]
  max=0;
  for(i=0;i<=word.length;i++){
    counts.push(0);
  }
  for(i=0;i<word.length;i++){
    counts[matchLengths[index][i]]++;
  }
  for(i=word.length-1;i>0;i--){
    if(counts[i]==3){
      max=i;
      break;
    }
    if(kmpArrays[index][i-1]){ //if this value has a smaller value it could be as well
      counts[kmpArrays[index][i]]+=counts[i-1];
    }
  }
  maxLengths.push(max);
}

Program wykorzystuje te dane, aby wyeliminować wszystkie podciągi, które nie pojawiają się dokładnie trzy razy i wszystkie podłańcuchy najdłuższych prawidłowych podłańcuchów.

for(index=0;index<word.length;index++){
  if(!maxLengths[index])
    continue;
  for(i=0;i<word.length;i++){
    if(matchLengths[index][i]==maxLengths[index]){
      tokens[i-maxLengths[index]+1]=maxLengths[index];
    }
  }
}

Następnie program ustawia wszystkie nakładające się lub częściowe podciągi do usunięcia.

for(index=0;index<word.length;index++){
  sStrs.push(word.substring(index,tokens[index]+index));
  for(i=1;i<tokens[index];i++){
    toRemove[index+i]=1;
    if(tokens[index]<tokens[index+i]+i){
      toRemove[index]=1;
    }
  }
}

Dla każdej z wartości, które mają zostać usunięte, usuwane są również wszystkie równoważne podciągi.

for(index=0;index<word.length;index++){
  if(toRemove[index]){
    removal=sStrs[index];
    for(i=0;i<3;i++){
      indxOf=sStrs.indexOf(removal);
      sStrs[indxOf]="";
      toRemove[indxOf]=0;
    }
  }
}

Wreszcie program łączy ze sobą szereg podciągów i wysyła je.