Pagini recente » Cod sursa (job #325488) | Cod sursa (job #2613149) | Cod sursa (job #2052108) | Cod sursa (job #1402354) | Cod sursa (job #2136563)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,i,j,q,p,t,h,e,d,v[1000001];
char a[2000001],c[2000001];
void RabinKarp( char a[], char c[], int q)
{
m=strlen(a);
n=strlen(c);
p=0;
t=0;
h=1;
for(i=0; i<m; i++)
{
h=(h*d)%q;
}
for(i=0; i<m; i++)
{
p=(d*p+a[i])%q;
t=(d*t+c[i])%q;
}
for(i=0; i<=n-m; i++)
{
if(p==t)
{
for(j=0; j<m; j++)
{
if(c[i+j]!=a[j])
break;
}
if(j==m)
{
e++;
v[e]=i;
}
}
if(i<n-m)
{
t=(d*(t-c[i]*h)+ c[i+m])%q;
if(t<0)
t=t+q;
}
}
}
int main()
{
f>>a;
f>>c;
q=101;
if(strlen(a)<=strlen(c))
RabinKarp( a,c,q);
g<<e<<endl;
for(i=1; i<=e; i++)
g<<v[i]<<" ";
}