Pagini recente » Cod sursa (job #1306600) | Cod sursa (job #3224744) | Cod sursa (job #2540056) | Cod sursa (job #2360085) | Cod sursa (job #1814344)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#define LEN 2000010
using namespace std;
int pi[LEN];
char pat[LEN], sir[LEN];
int patl,sirl;
vector<int> sol;
vector<int>::iterator it;
void precalc ( ){
int k = 0,i;
pi[1]=0;
for( i = 2 ; i <= patl ; i++){
while ( k > 0 && pat[k+1] != pat[i] ){
k = pi[k];
}
if ( pat [ k +1 ] == pat[i]){
k++;
}
pi[i]=k;
}
}
int main(){
int k,i,nrsol=0;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",pat+1);
scanf("%s",sir+1);
patl = strlen( pat+1 );
sirl = strlen( sir+1 );
precalc();
k=0;
for ( i = 1 ; i<=sirl ; i++){
while ( k >0 && pat[k+1] != sir[i] ){
k=pi[k];
}
if( pat[k+1] == sir[i] ){
k++;
}
if( k == patl ){
nrsol++;
if( sol.size() <= 1000 ){
sol.push_back( i - patl );
}
k=pi[k];
}
}
printf("%d\n",nrsol);
for( it= sol.begin() ; it != sol.end() ; it++ ){
printf("%d ",*it);
}
return 0;
}