Pagini recente » Cod sursa (job #2233184) | Cod sursa (job #1760451) | Cod sursa (job #1247749) | Cod sursa (job #1340893) | Cod sursa (job #1774005)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#define NM 2000010
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
int* pattern(string s) {
int *l = new int[NM];
int i = 1;
int j = 0;
l[0] = 0;
while (i < s.size()) {
if (s[i] == s[j]) {
l[i] = ++j;
++i;
} else {
if (j == 0) {
l[i] = 0;
++i;
} else {
j = l[j - 1];
}
}
}
return l;
}
vector <int> KMP(string t, string s) {
vector <int> a;
int *l = pattern(s);
int i = 0;
int j = 0;
while (i < t.size()) {
if (t[i] == s[j]) {
++i;
++j;
}
if (j == s.size()) {
a.push_back(i - j);
j = l[j - 1];
} else if (i < t.size() && t[i] != s[j]) {
if (j == 0) {
++i;
} else {
j = l[j - 1];
}
}
}
return a;
}
int main()
{
string s, test;
f >> s >> test;
vector <int> answer = KMP(test, s);
g << answer.size() << '\n' ;
int l = answer.size();
int k = min(1000, l);
for (int i = 0; i < k; ++i) {
g << answer[i] << ' ';
}
return 0;
}