Pagini recente » Cod sursa (job #2052737) | Cod sursa (job #2507389) | Cod sursa (job #1558313) | Cod sursa (job #2547019) | Cod sursa (job #1107338)
#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);
}