Pagini recente » Cod sursa (job #565465) | Cod sursa (job #1436855) | Cod sursa (job #1841212) | Cod sursa (job #1143430) | Cod sursa (job #2391731)
#include <bits/stdc++.h>
#define dim 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[dim],b[dim];
int pi[dim],pos[1024];
void MakePrefix()
{
int q=0;
pi[1]=0;
for(int i=2;i<=strlen(a+1);++i)
{
while(q&a[q+1]!=a[i])
q=pi[q];
if(a[q+1]==a[i])
++q;
pi[i]=q;
}
}
void Solve()
{
f>>(a+1)>>(b+1);
MakePrefix();
int q=0,ans=0;
for(int i=1;i<strlen(b+1);++i)
{
while(q&&a[q+1]!=b[i])
q=pi[q];
if(a[q+1]==b[i])++q;
if(q==strlen(a+1))
{
q=pi[q];
pos[++ans]=i-strlen(a+1);
}
}
g<<ans<<'\n';
for(int i=1;i<=ans;++i)
g<<pos[i]<<" ";
}
int main()
{
Solve();
return 0;
}