Pagini recente » Cod sursa (job #1231026) | Cod sursa (job #74910) | Cod sursa (job #212951) | Cod sursa (job #731155) | Cod sursa (job #1375310)
//Problem kmp
#include <cassert>
#include <cmath>
#include <cstdint>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main() {
string pattern, text;
getline(fin, pattern);
getline(fin, text);
int n = text.size(), m = pattern.size();
vector<int> pi(m);
for (int i = 1, p = 0; i < m; i += 1) {
while (p > 0 && pattern[i] != pattern[p]) p = pi[p - 1];
if (pattern[i] == pattern[p]) p += 1;
pi[i] = p;
}
vector<int> match;
for (int i = 0, p = 0; i < n; i += 1) {
while (p > 0 && text[i] != pattern[p]) p = pi[p - 1];
if (text[i] == pattern[p]) p += 1;
if (p == m) {
match.push_back(i - m + 1);
p = pi[p - 1];
}
}
fout << match.size() << '\n';
for (int i = 0; i < 1000 && i < int(match.size()); i += 1) {
fout << match[i] << ' ';
}
return 0;
}