Pagini recente » Cod sursa (job #1331236) | Cod sursa (job #2600450) | Cod sursa (job #2477858) | Cod sursa (job #678383) | Cod sursa (job #2417158)
#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>>(a+1)>>(b+1);
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;
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;
poz.push_back(i-n);
}
}
g<<ans<<'\n';
for(int i=0; i<ans; ++i)
g<<poz[i]<<" ";
return 0;
}