Pagini recente » Cod sursa (job #2758665) | Cod sursa (job #2248196) | Cod sursa (job #173496) | Cod sursa (job #731415) | Cod sursa (job #910697)
Cod sursa(job #910697)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
const int maxx=2000005;
string a,b;
int z[2*maxx],An,nrcomp;
vector <int> sol;
void read()
{
getline(std::cin,b);
a+='#'+b;
An=b.length();
getline(std::cin,b);
a+='#'+b;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
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.push_back(i-2-An);
}
}
printf("%d\n",nrcomp);
for(i=0;i<sol.size();i++)
printf("%d ",sol[i]);
printf("\n");
return 0;
}