Pagini recente » Cod sursa (job #1194093) | Cod sursa (job #1127049) | Cod sursa (job #1267401) | Cod sursa (job #371220) | Cod sursa (job #3329844)
#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[100001];
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 <=cnt; i++) {
out << v[i] << " ";
}
return 0;
}