Pagini recente » Cod sursa (job #2382526) | Cod sursa (job #1238623) | Clasament uuu | Cod sursa (job #2495982) | Cod sursa (job #3142256)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000010], b[2000010];
int lps[2000010], rez[1009];
int main()
{
int n, m, L, sol=0, i;
fin>>a+1>>b+1;
n=strlen(a+1);
m=strlen(b+1);
L=0;
lps[1]=0;
for(i=2;i<=n;i++)
{
while(L!=0&&a[i]!=a[L+1])
{
L=lps[L];
}
if(a[i]==a[L+1])
{
L++;
}
lps[i]=L;
}
L=0;
for(i=1;i<=m;i++)
{
while(L!=0&&b[i]!=a[L+1])
{
L=lps[L];
}
if(b[i]==a[L+1])
{
L++;
}
if(L==n)
{
sol++;
if(sol<1000)
{
rez[sol]=i-n;
}
L=lps[L];
}
}
fout<<sol<<"\n";
if(sol>1000)
{
sol=1000;
}
for(i=1;i<=sol;i++)
{
fout<<rez[i]<<" ";
}
return 0;
}