Pagini recente » Cod sursa (job #854295) | Cod sursa (job #1266792) | Cod sursa (job #3329845) | Cod sursa (job #1125520) | Cod sursa (job #3333329)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
int inc[2000001],f[2000001];
int main()
{
string s1, s2;
in >> s1 >> s2;
string s = s1 + "#" + s2;
int kmp[s.size()+1]={0};
kmp[1] = 0;
for (int i=2; i<=s.size(); i++) {
int l=kmp[i-1];
while (l>0 && s[l]!=s[i-1]) {
l=kmp[l];
}
if (s[l] == s[i - 1]) {
kmp[i] = l + 1;
}
}
int v[2000001];
int cnt=0;
for (int i=1; i<=s.size(); i++) {
if (kmp[i]==s1.size()) {
v[++cnt]=i-2*s1.size()-1;
}
}
out << cnt << "\n";
for (int i=1; i <=min(cnt,1000); i++) {
out << v[i] << " ";
}
return 0;
}