Pagini recente » Cod sursa (job #158146) | Cod sursa (job #2564574) | Cod sursa (job #245339) | Cod sursa (job #1702831) | Cod sursa (job #930424)
Cod sursa(job #930424)
#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] , ok =1;
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++;
if(ok)
Sol[nr] = i - La - 1;
if(nr == 1000)
ok = 0;
}
}
}
void print(){
g<<nr<<"\n";
for(i=1;i<=nr;i++)
g<<Sol[i]-La<<" ";
}
int main(){
read();
solve();
print();
return 0;
}