Cod sursa(job #2637289)

Utilizator andreic06Andrei Calota andreic06 Data 22 iulie 2020 12:35:34
Problema Prefix Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <iostream>
#include <fstream>

using namespace std;
const int N = 1e6;
int lps[N]; char sir[N];

int maxx;
void prefix_kmp ( int n ) {
   lps[0] = 0, maxx = -1;

   int len = 0;

   for ( int i = 1; i <= n; i ++ ) {
      while ( len > 0 && sir[len] != sir[i] )
         len = lps[len-1];
      if ( sir[i] == sir[len] )
        len ++;
      lps[i] = len;
      if ( lps[i] && ( i + 1 ) % ( i + 1 - lps[i] ) == 0 )
        maxx = i;
   }
}


ifstream fin ( "prefix.in" );
ofstream fout ( "prefix.out" );

int main()
{
   int t;
   fin >> t, fin.get ();

   while ( t -- ) {
      char ch = fin.get ();
      int n = 0;
      while ( ch != '\n' ) {
         sir[n++] = ch;
         ch = fin.get ();
      }

      prefix_kmp ( n );
      fout << maxx + 1 << '\n';

   }
    return 0;
}