Pagini recente » Cod sursa (job #549776) | Cod sursa (job #949126) | Cod sursa (job #3157452) | Cod sursa (job #360427) | Cod sursa (job #1456995)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAX = 2000005;
int pi[MAX], q, cnt;
char p[MAX], s[MAX];
vector <int> sol;
int main() {
fin >> p + 1 >> s + 1;
int l1 = strlen(p + 1), l2 = strlen(s + 1);
for (int i = 2; i <= l1; i++) {
while (q && p[q + 1] != p[i])
q = pi[q];
if (p[q + 1] == p[i])
q++;
pi[i] = q;
}
q = 0;
for (int i = 1; i <= l2; i++) {
while (q && p[q + 1] != s[i])
q = pi[q];
if (p[q + 1] == s[i])
q++;
if (q == l1) {
cnt++;
if (sol.size() < 1000)
sol.push_back(i - l1);
}
}
fout << cnt << '\n';
for (auto it : sol)
fout << it << ' ';
return 0;
}