Pagini recente » Cod sursa (job #1525259) | Cod sursa (job #1581695) | Cod sursa (job #302634) | Cod sursa (job #38852) | Cod sursa (job #1810087)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#define N 2000000
using namespace std;
char a [N], b[N];
int pi[N];
int lenb,lena;
vector <int> sol;
vector <int>::iterator it;
void precalc(){
int q=-1,i;
pi[0] = -1;
for(i=0 ; i < lena ; ){
while ( q>-1 && a[ q ] != a[i] ){
q = pi[q];
}
pi[++i] = ++q;
}
}
int main(){
int i,j,nrsol=0;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",a,b);
lena = strlen(a);
lenb = strlen(b);
precalc();
for(i =0 , j=0; j < lenb ; ){
while ( i > 0 && a[i] != b[j] ){
i = pi[i];
}
i++;
j++;
if ( i >= lena){
nrsol++;
if(sol.size() == 1000){
continue;
}
sol.push_back(j-i);
}
}
printf("%d\n",nrsol);
for( it = sol.begin() ; it != sol.end() ; it++){
printf("%d ",*it);
}
return 0;
}