Pagini recente » Cod sursa (job #1079439) | Cod sursa (job #2282273) | Cod sursa (job #1959895) | Cod sursa (job #2401633) | Cod sursa (job #2701880)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int kmp[2000001];
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string target, source, s;
fin >> target >> source;
s = "$" + target + "$" + source;
kmp[1] = 0;
for (int i = 2; i < s.size(); ++i) {
int answer = kmp[i - 1];
while(answer != 0 && s[answer + 1] != s[i]) {
answer = kmp[answer];
}
if (s[answer + 1] == s[i]) {
answer += 1;
}
kmp[i] = answer;
}
int cnt = 0;
for (int i = target.size() + 2; i < s.size(); ++i) {
if (kmp[i] == target.size()) {
cnt += 1;
}
}
fout << cnt << "\n";
for (int i = target.size() + 2; i < s.size(); ++i) {
if (kmp[i] == target.size()) {
cnt += 1;
if (cnt == 1001) {
break;
}
int result = i - 2 * target.size() - 1;
fout << result << " ";
}
}
return 0;
}