Pagini recente » Cod sursa (job #2772813) | Cod sursa (job #2213583) | Cod sursa (job #2268595) | Cod sursa (job #734198) | Cod sursa (job #930411)
Cod sursa(job #930411)
#include<fstream>
#include<string.h>
#define max_l 4000010
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[max_l] , b[max_l/2];
int La , Lb , i , fail , P[max_l] , nr , Sol[1010];
void read(){
f>>a+1>>b;
La = strlen(a+1);
Lb = strlen(b);
a[La+1] = '*'; strcpy(a+La+2 , b);
}
void solve(){
P[1] = 0;
for(i = 2 ; i <= La + Lb + 1 ; i++){
fail = P[i-1];
while(a[fail+1]!=a[i]&&fail!=0)
fail = P[fail];
if(a[fail+1] == a[i])
P[i] = fail+1;
if(P[i] == La){
nr++;
Sol[nr] = i - La - 1;
if(nr == 1000)
break;
}
}
}
void print(){
g<<nr<<"\n";
for(i=1;i<=nr;i++)
g<<Sol[i]-La<<" ";
}
int main(){
read();
solve();
print();
return 0;
}