Cod sursa(job #1107338)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 13 februarie 2014 20:37:10
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include<fstream>
#include<string>
#include<cstring>
using namespace std;
int i,j,n,m,sol[2005],z[2005];
string s;
bool ok=1;

int solve(int lin){
    s=' '+s;
    
    memset(z,0,sizeof(z));
    int l=0,r=0,i;
    z[1]=0;
    for (i=2; i<=m; ++i)
        if (i<=r) {
                  int p=i-l+1,d=r-i+1;
                  if (z[p]<d) z[i]=z[p];
                  else {
                       int p1=d+1, p2=r+1;
                       while (s[p1]==s[p2]) {++p1; ++p2;}
                       --p2;
                       z[i]=p2-i+1;
                       l=i; r=p2;
                       }
                  }
         else {
               int p1=1, p2=i;
                       while (s[p1]==s[p2]) {++p1; ++p2;}
                       --p2;
                       z[i]=p2-i+1;
                        if (z[i]!=0) { l=i; r=p2;}
               }
   for (i=2; i<=m; ++i)
    if ( z[i]==m-i+1) ++sol[i];
  /* if (lin==1) for (i=1; i<=m; ++i) sol[i]=z[i];
   else for (i=1; i<=m; ++i) if (z[i]<sol[i]) sol[i]=z[i]; */
}

int main(void){
    ifstream fin("map.in");
    ofstream fout("map.out");
    fin>>n>>m; getline(fin,s);
    for (i=1; i<=n; ++i) { getline(fin,s); solve(i);}
     sol[1]=n;
    for (i=m/2+(m%2); i>=1; --i)  
     if (sol[i]==n) { fout<<m-i+1; break; }
   
 return(0);
}