Pagini recente » Cod sursa (job #1272822) | Cod sursa (job #1499386) | Cod sursa (job #3171211) | Cod sursa (job #2051021) | Cod sursa (job #1232974)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
char a[2000001],b[2000001];
int n,m,cont,solutie[2000001];
bool verifica(int k)
{
bool ok; int i;
i=k; ok=true;
while(i<=k+n-1 && ok==true)
{
if (a[i-k]!=b[i])
ok=false;
else
i=i+1;
}
return(ok);
}
void RabinKarp(char s[], char sub[]) //se trimit sirurile de lungime n
//n e lungimea lui sub si m e lungimea lui s
{
int hs,hsub,i;
ofstream g("strmatch.out");
cont=0;
hs=0;
for (i=0; i<=n-1; i++)
hs=hs+s[i]-64;
hsub=0;
for (i=0; i<=n-1; i++)
hsub=hsub+sub[i]-64;
//cout<<hs<<" "<<hsub;
for (i=1; i<=m-n+1; i++)
{
if (hs == hsub)
if (verifica(i)==true)
{
solutie[cont]=i;
cont=cont+1;
}
hs=hs-s[i]+s[n+i+1];
}
g<<cont<<"\n";
for (i=0; i<=cont-1; i++)
g<<solutie[i]<<" ";
g.close();
}
void citire()
{
ifstream f("strmatch.in");
f>>a>>b;
n=strlen(a);
m=strlen(b);
f.close();
}
int main()
{
citire();
RabinKarp(b,a);
return(0);
}