Cod sursa(job #88631)

Utilizator mugurelionutMugurel-Ionut Andreica mugurelionut Data 3 octombrie 2007 11:44:55
Problema Prefix Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.13 kb
/* Mugurel Ionut Andreica - Bucuresti, ROMANIA */

/* Time Complexity: O(N) */

#include <stdio.h>
#include <string.h>
#define filein "prefix.in"
#define fileout "prefix.out"
#define maxn 1000001

char x[maxn];
int prefix[maxn], marcat[maxn];

int main()
{
int t, i, k, l, n, max;

freopen(filein, "r", stdin);
freopen(fileout, "w", stdout);

for (scanf("%d ", &t); t; t--)
  {
  gets(x);
  n = strlen(x);
  
  prefix[0] = k = -1;
  for (i = 1; i < n; i++)
    {
      while (k > -1 && x[k+1] != x[i])
        k = prefix[k];
  
      if (x[k+1] == x[i])
        k++;
  
      prefix[i] = k;
    }
  
  memset(marcat, 0, n*sizeof(int));
  for (max = 0, i = n-1; i >= 0; i--)
    {
      marcat[i] = 1;
      l = i-prefix[i];
  
      if (l == i+1)
        continue;
  
      k = prefix[i];
      while (k >= l && !marcat[k])
        {
          if (k-prefix[k] != l)
            break;
  
          marcat[k] = 1;
  
          k = prefix[k];
        }
  
      if (k == l-1 && i+1 > max)
        {
          max = i+1;
          break;
        }
    }
  
  printf("%d\n", max);
  }

return 0;
}