Pagini recente » Cod sursa (job #2206664) | Cod sursa (job #410188) | Cod sursa (job #1262584) | Istoria paginii runda/runda12 | Cod sursa (job #2114782)
#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 (int i=0;i<min(1000,(int)res.size());i++) g<<res[i]<<' ';
return 0;
}