Pagini recente » Cod sursa (job #372706) | Cod sursa (job #984269) | Cod sursa (job #2946198) | Cod sursa (job #2959815) | Cod sursa (job #2381968)
#include <bits/stdc++.h>
#define NM 5000002
using namespace std;
string a, b;
int n;
string s;
int kmp[NM];
vector <int> ans;
int main()
{
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
fin >> a >> b;
s += ' ';
s += a;
s += '$';
s += b;
n = s.size() - 1;
kmp[1] = 0;
for(int i = 2; i <= n; i++)
{
kmp[i] = kmp[i - 1];
while(kmp[i] > 0 && s[i] != s[kmp[i] + 1])
kmp[i] = kmp[kmp[i]];
if(s[i] == s[kmp[i] + 1])
kmp[i]++;
if(kmp[i] == a.size())
ans.push_back(i - 2 * kmp[i] - 1);
}
fout << ans.size() << "\n";
for(int i = 0; i < ans.size() && i < 1000; i++)
fout << i << " ";
fout << "\n";
return 0;
}