Pagini recente » Cod sursa (job #521095) | Cod sursa (job #2514062) | Cod sursa (job #3254323) | Cod sursa (job #2253245) | Cod sursa (job #909469)
Cod sursa(job #909469)
#include <cstdio>
#include <cstring>
#define nMax 2000100
using namespace std;
char a[nMax];
char b[nMax];
int k[nMax];
int n;
int m;
int na;
int afis[1002];
void citire(){
gets(a + 1);
gets(b + 1);
n = strlen(a + 1);
m = strlen(b + 1);
}
void prefix(){
int p = 0;
for(int i = 2; i <= n; ++ i){
while(p && a[i] != a[p + 1]){
p = k[p];
}
if(a[i] == a[p + 1]){
p ++;
}
k[i] = p;
}
}
void kmp(){
int p = 0;
for(int i = 1; i <= m; ++ i){
while(p && b[i] != a[p + 1]){
p = k[p];
}
if(b[i] == a[p + 1]){
p ++;
}
if(p == n){
if(na < 1000){
afis[na] = i - p;
}
na ++;
}
}
}
void afisare(){
printf("%d\n", na);
if(na > 1000){
na = 1000;
}
for(int i = 0; i < na; ++ i){
printf("%d ", afis[i]);
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
citire();
prefix();
kmp();
afisare();
return 0;
}