Pagini recente » Cod sursa (job #2334112) | Cod sursa (job #1189754) | Cod sursa (job #233412) | Cod sursa (job #757730) | Cod sursa (job #2238250)
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
#define NMAX 2000002
char a[NMAX], b[NMAX];
int pi[NMAX];
void prefix(char s[], int n) {
int q = 0;
pi[1] = 0;
for (int i = 2; i <= n; i++) {
while (q && s[i] != s[q + 1])
q = pi[q];
if (s[i] == s[q + 1])
q++;
pi[i] = q;
}
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f >> (a + 1) >> (b + 1);
int n = strlen(a + 1);
int m = strlen(b + 1);
prefix(a, n);
vector <int> sol;
int q = 0, cnt = 0;
for (int i = 1; i <= m; i++) {
while (q && b[i] != a[q + 1])
q = pi[q];
if (b[i] == a[q + 1])
q++;
if (q == n) {
cnt++;
if (cnt <= 1000)
sol.push_back(i - n);
q = pi[n];
}
}
g << cnt << '\n';
for (const auto& x:sol) {
g << x << " ";
}
g.close();
return 0;
}