Pagini recente » Cod sursa (job #359598) | Cod sursa (job #3178346) | Cod sursa (job #2887310) | Cod sursa (job #1636248) | Cod sursa (job #2897548)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
#define DIM 2000001
#define int long long int
int m,n,t,p,rasp[DIM],r;
char P[DIM],T[DIM];
void potrivire_rabin_karp(int d,int q){
int h=1;
for(int i=0;i<m-1;i++){
h=(d*h)%q;
}
h%=q;
p=0;int tempT;
for(int i=0;i<m;i++){
p=(d*p+(int)P[i])%q;
tempT=((d*t)+(int)T[i]);
t=tempT%q;
}
for(int s=0;s<=n-m;s++){
if(p==t){
bool ok=true;
for(int j=0;j<m;j++)
{
if(P[j]!=T[s+j]){
ok=false;
break;
}
}
if(ok && r<1000){
rasp[r]=s;
r++;
}
}
tempT=((d*(t-T[s]*h)+(int)T[s+m]));
t=tempT%q;
if(t<0){
t+=q;
}
}
}
main(){
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin>>P>>T;
m=strlen(P);
n=strlen(T);
potrivire_rabin_karp(10000000000,57);
fout<<r<<'\n';
for(int i=0;i<r;i++){
fout<<rasp[i]<<' ';
}
}