Pagini recente » Cod sursa (job #1449604) | Cod sursa (job #2828461) | Cod sursa (job #2354166) | Cod sursa (job #2952835) | Cod sursa (job #3168487)
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 2e6+5;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n, m, t, p[N];
char a[N], b[N], aux[N];
vector<int> r;
int main()
{
f >> a >> b;
int n = strlen(a), m = strlen(b);
strcat(aux, "#"); strcat(aux, a); strcpy(a, aux);
strcpy(aux, "");
strcat(aux, "*"); strcat(aux, b); strcpy(b, aux);
if (n > m) {g << 0; return 0;}
for (int i = 2; i <= n; i++){
int k = p[i-1];
while (k && a[i] != a[k+1]) k = p[k];
if (a[i] == a[k+1]) k++;
p[i] = k;
}
int k = 0;
for (int i = 1; i <= m; i++){
while (k && b[i] != a[k+1]) k = p[k];
if (b[i] == a[k+1]) k++;
if (k == n){
t++; k = p[n];
if (t <= 1000) r.pb(i-n);
}
}
g << t << '\n';
for (auto it: r) g << it << ' ';
return 0;
}