Pagini recente » Cod sursa (job #1277825) | Cod sursa (job #124572) | Cod sursa (job #910947) | Cod sursa (job #1837485) | Cod sursa (job #1779766)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int NMAX = 2000002;
char pattern[NMAX];
char text[NMAX];
int sol[NMAX];
int prime=101;
int d=256;
int k=0;
void rabinkarp(int n,int m)
{
int hashpat = 0;
int hashtxt = 0;
int pow = 1;
int i,j;
for(i=0; i<n-1; i++)
{
pow=(pow*d)%prime;
}
for(i=0; i<n; i++)
{
hashpat=(hashpat*d + pattern[i])%prime;
hashtxt=(hashtxt*d + text[i])%prime;
}
for(i=0; i<=m-n; i++)
{
if(hashpat==hashtxt)
{
for(j=0; j<n; j++)
{
if(pattern[j]!=text[i+j])
break;
}
if(j==n)
{
sol[k]=i;
k++;
}
}
if(i<m-n)
{
hashtxt=(d*(hashtxt-text[i]*pow)+text[i+n])%prime;
if(hashtxt<0)
hashtxt=hashtxt+prime;
}
}
}
int main()
{
in>>pattern;
in>>text;
int n = strlen(pattern);
int m = strlen(text);
if(n>m)
{
out<<0;
return 0;
}
rabinkarp(n,m);
out<<k<<'\n';
for(int i=0;i<k && i<1000;i++)
{
out<<sol[i]<<" ";
}
}