Pagini recente » Cod sursa (job #2050570) | Cod sursa (job #1576409) | Cod sursa (job #358674) | Cod sursa (job #2726792) | Cod sursa (job #2417161)
#include <bits/stdc++.h>
#define dim 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[dim],b[dim];
int pref[dim];
vector <int> poz;
int main()
{
f.getline(a+1,dim);
f.getline(b+1,dim);
int n=strlen(a+1),m=strlen(b+1),k=0;
for(int i=2; i<=n; ++i)
{
while(k&&a[k+1]!=a[i])
k=pref[k];
if(a[k+1]==a[i])
++k;
pref[i]=k;
}
int ans=0;
k=0;
for(int i=1; i<=m; ++i)
{
while(k&&a[k+1]!=b[i])
k=pref[k];
if(a[k+1]==b[i])
++k;
if(k>=n)
{
++ans;
if(ans<=1000)poz.push_back(i-n);
}
}
g<<ans<<'\n';
for(int i=0; i<poz.size(); ++i)
g<<poz[i]<<" ";
return 0;
}