Pagini recente » Cod sursa (job #546589) | Cod sursa (job #585326) | Cod sursa (job #2290545) | Cod sursa (job #503652) | Cod sursa (job #2702057)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int kmp[4000005];
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;
if (cnt > 1000) {
break;
}
}
}
fout << cnt << "\n";
for (int i = target.size() + 2; i < s.size(); ++i) {
if (kmp[i] == target.size()) {
cnt += 1;
if (cnt <= 1000) {
int result = i - 2 * target.size();
fout << result << " ";
}
}
}
return 0;
}