Contexte

Incident est un langage de programmation assez inhabituel, dans la mesure où sa liste de jetons n'est pas prédéterminée, mais plutôt déduite de l'entrée. En tant que tel, la tokenisation d'un programme Incident peut être assez difficile, surtout si vous voulez le faire efficacement. Cette tâche consiste à le faire vous-même.

La tâche

Votre programme recevra une chaîne en entrée. Voici l'algorithme utilisé par Incident pour le tokeniser:

1. Identifiez toutes les chaînes qui se produisent en tant que sous-chaîne de l'entrée de trois manières exactement (c'est-à-dire qu'il y a exactement trois occurrences de cette chaîne dans l'entrée).
2. Supprimez l'une de ces chaînes qui sont une sous-chaîne d'une autre chaîne de ce type (par exemple, pour l'entrée ababab, la seule chaîne restante serait ab, non aou b, car aet bsont les deux sous-chaînes de ab).
3. Ignorez toutes les chaînes qui se chevauchent dans l'entrée. (Par exemple, aaaacontient exactement trois copies de aa, mais ces copies se chevauchent aux deuxième et troisième caractères, elles seront donc supprimées. De même, dans abababa, il y a trois copies de abet trois copies de ba, mais les deuxième à sixième caractères se trouvent chacun au chevauchement de an abet a ba, donc les deux abet baseraient rejetés).
4. Toutes les chaînes qui restent à ce stade sont les jetons utilisés par le programme. Tokenisez l'entrée d'origine dans une séquence de ces jetons (en raison de la suppression à l'étape précédente, il n'y aura qu'une seule façon de le faire). Tous les caractères de l'entrée qui ne font partie d'aucun jeton sont traités comme des commentaires et supprimés.

Votre programme doit prendre une chaîne en entrée et renvoyer la tokenisation correspondante de la chaîne (une liste de jetons, chacun étant exprimé sous forme de chaînes) en sortie. De plus, cela doit être fait au moins modérément efficacement; en particulier, le programme doit fonctionner en temps quadratique ("O (n²)") ou mieux. (Par ailleurs, il est presque certainement possible d'aller plus vite que quadratique, mais ce n'est pas l' algorithme le plus rapide , alors n'hésitez pas à utiliser l'algorithme le plus ters que vous pouvez trouver qui correspond aux limites de la complexité.)

Clarifications

• Bien que les programmes d'incident puissent en théorie contenir n'importe lequel des 256 octets, il est acceptable dans le cadre de ce défi que votre programme ne gère que les entrées formées en ASCII imprimable (y compris l'espace), plus la nouvelle ligne et l'onglet. (Tous les programmes d'incident connus se limitent à ce sous-ensemble). Notez que l'espace / nouvelle ligne / tabulation n'est pas spécial et peut apparaître au milieu des jetons; L'incident traite les 256 octets comme opaques.
• La définition du "temps quadratique" est "si la taille de l'entrée est doublée, le programme fonctionnera plus lentement d'une constante plus un facteur de 4", c'est-à-dire si t ( x ) est le temps maximum que prend votre programme pour traiter une entrée de taille x , alors il doit y avoir une constante k telle que t (2  x ) <4  t ( x ) + k pour tout x . Gardez à l'esprit que la comparaison des chaînes prend du temps proportionnel à la longueur des chaînes.
• Votre programme devrait théoriquement être capable de gérer des programmes d'entrée de n'importe quelle longueur s'il est exécuté dans une variante (éventuellement hypothétique) de votre langue qui a une mémoire illimitée et utilise des nombres entiers illimités (c'est OK si le programme ne parvient pas à atteindre cet objectif lorsqu'il est exécuté dans la pratique en raison de les entiers ou la mémoire du langage étant en fait finement grands). Vous pouvez supposer (aux fins du calcul de la complexité) que les entiers qui ne dépassent pas la longueur de l'entrée peuvent être comparés en temps constant (bien que gardez à l'esprit que si vous utilisez des valeurs plus grandes, par exemple en raison de la conversion de l'entrée en un entier unique, ils mettront un certain temps à comparer proportionnellement au nombre de chiffres dont ils disposent).
• Vous pouvez utiliser n'importe quel algorithme qui respecte les limites de la complexité, même s'il ne suit pas les mêmes étapes que l'algorithme publié ci-dessus, tant qu'il produit les mêmes résultats.
• Ce puzzle consiste à tokeniser l'entrée, pas vraiment à formater la sortie. Si le moyen le plus naturel de produire une liste dans votre langue implique un format ambigu (par exemple, séparé par des sauts de ligne lorsque les chaînes contiennent des sauts de ligne littéraux, ou sans délimiteurs entre les chaînes), ne vous inquiétez pas du fait que la sortie finit par être ambiguë ( tant que la liste est réellement construite). Vous souhaiterez peut-être créer une deuxième version de votre soumission qui produira une sortie sans ambiguïté, pour faciliter les tests, mais la version d'origine est la version qui compte pour la notation.

Cas de test

Pour la chaîne d'entrée suivante:

aaabcbcbcdefdfefedghijghighjkllkklmmmmonono-nonppqpq-pqprsrsrstststuvuvu

votre programme devrait produire la liste de sortie suivante:

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

Condition de victoire

Il s'agit de code-golf , donc le programme valide le plus court (c'est-à-dire un comportement d'entrée / sortie correct et suffisamment rapide pour s'exécuter), mesuré en octets, gagne.

C (gcc), 324 octets

La fonction fprend une chaîne terminée par un caractère nul et imprime les jetons sur stdout. Toutes les nouvelles lignes peuvent être supprimées du code ci-dessous.

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);
}
}

Cette ancienne version de 376 octets est un peu plus facile à lire; l'explication ci-dessous s'y applique.

*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)génère la table tde modèle ppour l'algorithme Knuth – Morris – Pratt. K(c)traiter le caractère suivant cde la chaîne de recherche et les mises à jour m, dont la longueur du plus grand préfixe ppeut se trouver se terminant par le dernier caractère traité.

Dans la première forboucle, pour chaque index ade la chaîne, nous comptons le nombre de fois où chaque valeur possible de mse produit lors de la recherche dans la chaîne entière de la sous-chaîne commençant à a. Ensuite, nous recherchons le plus grand ltel que la lsous-chaîne de longueur commençant à as'est produite exactement 3 fois. S'il est suffisamment court pour être entièrement contenu par une chaîne trouvée pour un précédent a, nous l'ignorons. S'il se chevauche, nous supprimons la chaîne précédente de z, l'enregistrement de tableau dont les jetons seront conservés. Sinon, sa longueur est stockée dans z.

Ensuite, nous utilisons à nouveau KMP pour rechercher dans la chaîne les jetons enregistrés dans z. Si l'un d'eux se trouve à un emplacement avec une entrée 0 z, nous savons que ce jeton a été supprimé en raison d'un chevauchement. Si le jeton n'a pas été supprimé, il est imprimé.

JavaScript, 878 867 842 825 775 752 717 712 704 673 664 650 641 octets

Merci à @Kritixi Lithos d'avoir aidé
à jouer au code Merci à @ User2428118 d'avoir joué au golf 14 octets

(Ne fonctionnera pas dans IE7) (Les sauts de ligne doivent être entrés comme " \n" et les tabulations comme " \t" dans la chaîne d'entrée, tous les caractères Unicode doivent être entrés comme \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``}

Essayez-le en ligne

Explication du fonctionnement et du code non golfé

Premièrement, le programme génère des tableaux Knuth Morris Pratt pour chaque sous-chaîne possible;

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);
}

Ensuite, le programme trouve les longueurs maximales correspondantes à chaque index unique du mot avec chaque sous-chaîne. (c'est O (n ^ 2) fois)

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);
}

Le programme utilise ces données pour trouver les sous-chaînes les plus longues qui apparaissent trois fois pour chaque caractère de départ dans la chaîne.

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);
}

Le programme utilise ces données pour éliminer toutes les sous-chaînes qui n'apparaissent pas exactement trois fois et toutes les sous-chaînes des sous-chaînes valides les plus longues.

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];
    }
  }
}

Ensuite, le programme définit toutes les sous-chaînes superposées ou partielles comme devant être supprimées.

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;
    }
  }
}

Pour chacune des valeurs à supprimer, toutes les sous-chaînes équivalentes sont également supprimées.

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;
    }
  }
}

Enfin, le programme joint le tableau de sous-chaînes et le génère.