Pagini recente » Cod sursa (job #807414) | Cod sursa (job #3355963) | Cod sursa (job #3355906) | Cod sursa (job #3340417) | Cod sursa (job #3348102)
#include <bits/stdc++.h>
using namespace std;
const int Nmax=2e6+5;
int n,pi[Nmax];
void kmp(string s) {
int k=0;
for (int i=1; i<n; ++i) {
while (k && s[k]!=s[i]) k=pi[k-1];
if (s[k]==s[i]) k++;
pi[i]=k;
}
}
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string a,b;
cin>>a>>b;
n=a.size();
int m=b.size();
kmp(a);
vector<int> ans;
int k=0,lim=1000;
for (int i=0; i<m; ++i) {
while (k && a[k]!=b[i]) k=pi[k-1];
if (a[k]==b[i]) k++;
if (k==n) {
ans.push_back(i-n+1);
k=pi[k-1];
}
}
cout<<ans.size()<<'\n';
for (int i=0; i<min((int)ans.size(),lim); ++i) cout<<ans[i]<<' ';
cin.close();
cout.close();
return 0;
}