Pagini recente » Cod sursa (job #1436227) | Cod sursa (job #2973337) | Cod sursa (job #68202) | Cod sursa (job #595310) | Cod sursa (job #1375226)
//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;
fin >> pattern >> 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];
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);
}
}
fout << match.size() << '\n';
for (int i = 0; i < 1000 && i < int(match.size()); i += 1) {
fout << match[i] << ' ';
}
return 0;
}