Pagini recente » Cod sursa (job #1064225) | Cod sursa (job #751084) | Cod sursa (job #631920) | Cod sursa (job #2202513) | Cod sursa (job #2863073)
#include <fstream>
#include <iostream>
#include <vector>
#define NMAX 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string w, s;
int N;
int T[NMAX];
void createPartialMatchTable() {
T[0] = 0;
int j = 0;
for (int i = 1; i < w.length(); ++i) {
if (w[j] == w[i]) {
T[i] = j + 1;
++j;
}
else {
while (w[i] != w[j] && j > 0) {
j = T[j - 1];
}
if (j == 0 && w[i] != w[j]) {
T[i] = 0;
}
else
T[i] = ++j;
}
}
}
vector<int> solutions;
void kmp() {
int j = 0;
for (int i = 0; i < s.length(); ++i) {
if (s[i] == w[j]) {
++j;
if (j == w.length()) {
solutions.push_back(i - w.length() + 1);
j = T[j - 1];
}
}
else {
while (s[i] != w[j] && j > 0) {
j = T[j - 1];
}
if (s[i] == w[j]) {
++j;
}
}
}
}
int main()
{
fin >> w >> s;
createPartialMatchTable();
kmp();
int N = min(solutions.size(), (size_t)1000);
fout << N << "\n";
for (int i = 0; i < N; ++i) {
fout << solutions[i] << " ";
}
return 0;
}