Pagini recente » Cod sursa (job #2353697) | Cod sursa (job #2407522) | Cod sursa (job #1600887) | Cod sursa (job #2131200) | Cod sursa (job #910701)
Cod sursa(job #910701)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int maxx=2000005;
string a,b;
int z[2*maxx],An,nrcomp,sol[1005];
void read()
{
getline(f,b);
a+='#'+b;
An=b.length();
getline(f,b);
a+='#'+b;
}
int main()
{
read();
int i,n=a.length(),l=1,r=1,j;
z[1]=An;
for(i=2;i<=n;i++)
{
if(i>r)
{
for(j=1;i+j-1<=n && a[i+j-1]==a[j];j++);
z[i]=j-1;
if(j-1)
{
l=i;
r=i+z[i]-1;
}
}
else
if(z[i-l+1]<r-i+1)
z[i]=z[i-l+1];
else
{
if(z[i-l+1]>r-i+1)
z[i]=r-i+1;
else
{
for(++r,j=z[i-l+1]+1;r<=n && a[r]==a[j];r++,j++);
r--; j--;
z[i]=j;
l=i;
}
}
if(z[i]==An)
{
nrcomp++;
if(nrcomp<=1000)
sol[nrcomp]=i-An-2;
}
}
g<<nrcomp<<"\n";
for(i=1;i<=min(1000,nrcomp);i++)
g<<sol[i]<<" ";
g<<"\n";
return 0;
}