Pagini recente » Cod sursa (job #1960959) | Cod sursa (job #807238) | Cod sursa (job #1312660) | Cod sursa (job #477611) | Cod sursa (job #2857988)
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
#define NMAX 2000005
int n, m, cnt, nr, lps[NMAX], ans[NMAX];
char pat[NMAX], txt[NMAX];
void init_lps()
{
int len = 0, i = 1;
lps[0] = 0;
while(i < n){
if (pat[i] == pat[len]){
len ++;
lps[i] = len;
i ++;
}else{
if (len != 0){
len = lps[len - 1];
}else{
lps[i] = 0;
i++;
}
}
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(pat, sizeof(pat), stdin);
fgets(txt, sizeof(txt), stdin);
for ( ; isdigit(pat[n]) || isalpha(pat[n]); n++);
for ( ; isdigit(txt[m]) || isalpha(txt[m]); m++);
init_lps();
int i = 0;
int j = 0;
while(i < m){
if (pat[j] == txt[i]){
i ++;
j ++;
}
if (j == n){
cnt ++;
ans[cnt] = i - j;
j = lps[j - 1];
}else if (i < m && pat[j] != txt[i]){
if (j != 0){
j = lps[j - 1];
}else{
i ++;
}
}
}
printf("%d\n", cnt);
for (int i=1;i<=min(1000, cnt);i++){
printf("%d ", ans[i]);
}
printf("\n");
return 0;
}