Cod sursa(job #1133071)

Utilizator Kira96Denis Mita Kira96 Data 4 martie 2014 13:09:19
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#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;
}