Pagini recente » Cod sursa (job #2349054) | Cod sursa (job #2239089) | Cod sursa (job #1006187) | Cod sursa (job #1074275) | Cod sursa (job #2381960)
#include <bits/stdc++.h>
#define NM 2000002
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.size() < 1000)
ans.push_back(i - 2 * kmp[i] - 1);
}
fout << ans.size() << "\n";
for(auto i : ans)
fout << i << " ";
fout << "\n";
return 0;
}