Pagini recente » Cod sursa (job #2981058) | Cod sursa (job #2037733) | Cod sursa (job #1777000) | Cod sursa (job #3126951) | Cod sursa (job #1498596)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int NMAX = 2000004;
char P[NMAX], T[NMAX];
int pi[NMAX], n, m;
vector <int> sol;
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(P + 1);
gets(T + 1);
P[0] = T[0] = '#';
n = strlen(P) - 1;
m = strlen(T) - 1;
P[0] = T[0] = 0;
int rasp = 0;
int k = 0;
for(int i = 2; i <= n; ++ i) {
while(k > 0 && P[k + 1] != P[i])
k = pi[k];
if(P[k + 1] == P[i])
++ k;
pi[i] = k;
}
k = 0;
for(int i = 1; i <= m; ++ i) {
while(k > 0 && P[k + 1] != T[i])
k = pi[k];
if(P[k + 1] == T[i])
++ k;
if(k == n) {
k = pi[n];
++ rasp;
if(rasp <= 1000)
sol.push_back(i - n + 1);
}
}
printf("%d\n", rasp);
for(int i = 0; i < sol.size(); ++ i)
printf("%d ", sol[i] - 1);
return 0;
}