Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Istoria paginii utilizator/tudormanoleasa | Monitorul de evaluare | Cod sursa (job #1165362)
#include<fstream>
#include<cstring>
#include<cstdlib>
#include<ctime>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int Nmax = 2000001;
char A[Nmax],B[Nmax];
int a,b,pi[Nmax];
int many,Ans[1001];
void KMP(){
int w=0;
for(int i=1;i<a;i++){
while(w!=0 && A[w]!=A[i]) w=pi[w-1];
if(A[w]==A[i]) w++;
pi[i]=w;
}
w=0;
for(int i=0;i<b;i++){
while(w!=0 && A[w]!=B[i]) w=pi[w-1];
if(A[w]==B[i]) w++;
if(w==a) if(++many<=1000) Ans[many]=i-a+1;
}
}
const int base = 73;
int code(char c){
if('a'<=c && c<='z') return (int(c)-'a'+1);
if('Z'<=c && c<='Z') return (int(c)-'A'+29);
if('0'<=c && c<='9') return (int(c)-'0'+59);
}
void RabinKarp(){
unsigned int id=0,idn=0,pow=1;
for(int i=0;i<a;i++) id=id*base+code(A[i]),pow=pow*base;
for(int i=0;i<b;i++){
idn=idn*base+code(B[i]);
if(i>=a) idn-=pow*code(B[i-a]);
if(id==idn) if(++many<=1000) Ans[many]=i-a+1;
}
}
int main(){
in.getline(A,Nmax);a=strlen(A);
in.getline(B,Nmax);b=strlen(B);
srand(time(NULL));
if(rand()%2==0) KMP();
else RabinKarp();
out<<many<<'\n';
for(int i=1;i<=min(many,1000);i++) out<<Ans[i]<<' ';out<<'\n';
return 0;
}