Pagini recente » Cod sursa (job #1155192) | Cod sursa (job #2750831) | Cod sursa (job #1340185) | Cod sursa (job #1864263) | Cod sursa (job #1166530)
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define len(x) int((x).size())
vector<int> res;
vector<int> pi;
void compute_prefix(const string &s);
void find_match(const string &s, const string &t);
int main() {
string P, T;
fin >> P >> T;
P = " " + P;
T = " " + T;
compute_prefix(P);
find_match(P, T);
fout << len(res) << '\n';
for (int i = 0; i < len(res) && i < 1000; i += 1) {
fout << res[i] << ' ';
}
}
void compute_prefix(const string &s) {
int n = len(s) - 1;
pi.resize(n + 1);
for (int i = 2, p = 0; i <= n; i += 1) {
while (p > 0 && s[i] != s[p + 1]) p = pi[p];
if (s[i] == s[p + 1]) p += 1;
pi[i] = p;
}
}
void find_match(const string &s, const string &t) {
int n = len(t) - 1, m = len(s) - 1;
for (int i = 1, p = 0; i <= n; i += 1) {
while (p > 0 && s[p + 1] != t[i]) p = pi[p];
if (s[p + 1] == t[i]) p += 1;
if (p == m) {
res.push_back(i - m);
}
}
}