Pagini recente » Cod sursa (job #2436943) | Cod sursa (job #698813) | Cod sursa (job #431268) | Cod sursa (job #1120477) | Cod sursa (job #2849698)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int maxn=2e6+55;
int lsp[maxn];
char pat[maxn],txt[maxn];
int z[maxn];
int ans[maxn],cnt=0;
int main()
{
int l1,l2;
cin>>(pat+1);
cin>>(txt+1);
l1=strlen(pat+1);
l2=strlen(txt+1);
int l,r;
l=r=0;
for(int i=2; i<=l1; ++i)
{
if(i>r)
{
l=r=i;
while(r<=l1&&pat[r-l+1]==pat[r])
{
lsp[r]=max(lsp[r],r-l+1);
++r;
}
r--;
z[i]=r-l+1;
}
else
{
if(z[i-l+1]+i-1<r)
z[i]=z[i-l+1];
else
{ r=l=i;
while(r<=l1&&pat[r-l+1]==pat[r])
{
lsp[r]=max(lsp[r],r-l+1);
++r;
}
r--;
z[i]=r-l+1;
}
}
lsp[r]=max(lsp[r],r-l+1);
}
// for(int i=1;i<=l1;++i)
// cout<<lsp[i]<<" ";
int i1,i2;
i1=i2=1;
for(int i=1;i<=l2;++i)
{
if(pat[i1]!=txt[i])
i1=max(1,lsp[i1-1]+1);
else
{
++i1;
if(i1>l1)
{
ans[++cnt]=i-l1+1;
i1=max(lsp[l1]+1,1);
}
}
}
cout<<cnt<<'\n';
for(int i=1;i<=min(1000,cnt);++i)
cout<<ans[i]-1<<" ";
return 0;
}