Pagini recente » Cod sursa (job #2753045) | Cod sursa (job #720247) | Cod sursa (job #1787740) | Cod sursa (job #1363976) | Cod sursa (job #1773995)
#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[s.size() + 2];
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' ;
for (vector <int>::iterator it = answer.begin(); it != answer.end(); ++it) {
g << *it << ' ';
}
return 0;
}