Pagini recente » Cod sursa (job #2461326) | Cod sursa (job #490117) | Cod sursa (job #2171536) | Cod sursa (job #606197) | Cod sursa (job #963027)
Cod sursa(job #963027)
#include <string>
#include <queue>
#include <cstdio>
#include <iostream>
#define NMAX 2000001
int main(){
std::string A, B;
std::queue<int> sol;
int i, k, q, n, m, nr = 0;
int pi[NMAX];
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
std::cin >> A >> B;
n = A.size();
m = B.size();
for(i = 0; i < n; i++)
A[i] = toupper(A[i]);
for(i = 0; i < m; i++)
B[i] = toupper(B[i]);
A.insert(0, " ");
B.insert(0, " ");
k = 0;
pi[0] = 0;
for(i = 2; i <= n; i++){
while(k && A[k + 1] != A[i])
k = pi[k];
if (A[k + 1] == A[i])
++k;
pi[i] = k;
}
q = 0;
for(i = 1; i <= m; i++){
while(q && A[q + 1] != B[i])
q = pi[q];
if (A[q + 1] == B[i])
++q;
if (q == n)
sol.push(i - n), ++nr;
}
printf("%d\n", nr);
for(i = 0; i < 1000 && i < nr; i++)
printf("%d ", sol.front()),sol.pop();
printf("\n");
return 0;
}