Pagini recente » Cod sursa (job #2554157) | Cod sursa (job #2725203) | Cod sursa (job #871017) | Cod sursa (job #996647) | Cod sursa (job #2850257)
#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 q = 0;
int len=0;
for (int i = 2; i <= l1; ++i)
{ int nlen=max(len,1);
if(pat[len+1]==pat[i])
{
++len;
lsp[i]=len;
}
else
{
if(len)
{
len=lsp[len-1];
i--;
}
else
{
len=0;
lsp[i]=0;
}
}
}/*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++;
if(i1>l1)
{
i1=lsp[l1]+1;
ans[++cnt]=i-l1;
}
}
else
{
i1=lsp[i1-1]+1;
}
}
cout<<cnt<<'\n';
for(int i=1;i<=min(1000,cnt);++i)
cout<<ans[i]<<" ";
return 0;
}