Cod sursa(job #152560)

Utilizator cretuMusina Rares cretu Data 9 martie 2008 15:51:44
Problema Prefix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <string>

using namespace std;

int pi[1000000];

ofstream fout("prefix.out");

void Prefix(string s)
{
     int n = s.length();
     int i, k;
     string s2;
     
     s2 += " ";
     s2 += s;
         
     pi[1] = 0;
     k = 0;
     
     for (i = 2; i <= n; i++)    
     {
         while (k > 0 && s2[k+1] != s2[i]) {k = pi[k];}    
         if (s2[k+1] == s2[i]) k++;
         pi[i] = k;
     }
     
     int max = 0, maxi = 0;
     
     for (i = 1; i <= n; i++)
     {
          if (pi[i] > max && pi[i]%(i-pi[i]) == 0)        
          {
              max = pi[i];
              maxi = i;          
          }
     }
     fout << maxi << "\n";    
}

int main()
{
    ifstream fin("prefix.in");
    int T, q;
    string s;
    
    fin >> T;
    for (q = 1; q <= T; q++)    
    {
        fin >> s;
        Prefix(s);    
    }
    fin.close();
    fout.close();
    
    return 0;
}