Pagini recente » Cod sursa (job #801764) | Cod sursa (job #2006146) | Cod sursa (job #2470843) | Cod sursa (job #1282543) | Cod sursa (job #1133071)
#include<iostream>
#include<fstream>
//#define f cin
#define g cout
#include<cstring>
#include<algorithm>
#define N 1000100
using namespace std;
ifstream f("a.in");
long long key[N];
char s[N];
int sa[N],k,j,lcom,OK,dif,co,com,lcp[N],rank[N],i,n;
struct Cmp { bool operator()(int i, int j) const { return key[i]<key[j]; } };
void build()
{
for(i=0;i<n;++i)
{
key[i]=s[i];
sa[i]=i;
}
sort(sa,sa+n,Cmp());
for(k=1;k<n;k<<=1)
{
for(i=0;i<n;++i)
if(!i||key[sa[i]]!=key[sa[i-1]])
rank[sa[i]]=i;
else
rank[sa[i]]=rank[sa[i-1]];
if(k>=n)
return;
for(i=0;i<n;++i)
if(i+k<n)
key[i]=1LL*rank[i]*(n+1)+rank[i+k]+1;
else
key[i]=1LL*rank[i]*(n+1);
sort(sa,sa+n,Cmp());
}
for(i=0,k=0;i<n;++i)
{
if(k)
k--;
if(rank[i]==n-1)
{
k=0;
continue;
}
j=sa[rank[i]+1];
while(s[i+k]==s[j+k]) k++;
lcp[rank[i]]=k;
}
}
int main ()
{
while(1)
{
f>>s;
if(s[0]=='.')
return 0;
n=strlen(s);
build();
lcom=sa[rank[0]+1];
com=lcp[rank[0]];
i=sa[rank[0]+1];
OK=0;
if(com>=lcom)
OK=1;
while(OK)
{
if(i==n-1)
break;
dif=sa[rank[i]]-sa[rank[i]-1];
co=lcp[rank[i]];
if(co<dif||dif!=lcom)
OK=0;
}
if(OK)
g<<n/com<<"\n";
else
g<<"1\n";
}
return 0;
}