Pagini recente » Cod sursa (job #3168416) | Cod sursa (job #1478646) | Cod sursa (job #602020) | Cod sursa (job #3265698) | Cod sursa (job #2705055)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int kmp[4000011];
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;
}