Pagini recente » Cod sursa (job #756922) | Cod sursa (job #2253520) | Borderou de evaluare (job #804514) | Cod sursa (job #2577269) | Cod sursa (job #2114778)
#include <bits/stdc++.h>
#define Nmax 2000002
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int k,n,m,p[Nmax];
char a[Nmax],b[Nmax];
vector<int> res;
int main()
{
f>>a+1>>b+1;
n = strlen(a+1);
m = strlen(b+1);
k = 0;
for (int i=2;i<=n;i++){
while (k!=0 && a[k+1]!=a[i]) k = p[k];
if (a[k+1]==a[i]) k++;
p[i] = k;
}
k = 0;
for (int j=1;j<=m;j++){
while (k!=0 && a[k+1]!=b[j]) k = p[k];
if (a[k+1]==b[j]) k++;
if (k==n) res.push_back(j-n);
}
g<<res.size()<<'\n';
for (auto it : res) g<<it<<' ';
return 0;
}