Pagini recente » Cod sursa (job #720044) | Cod sursa (job #768925) | Borderou de evaluare (job #1414106) | Cod sursa (job #579744) | Cod sursa (job #2045258)
#include <fstream>
#include <string.h>
#define PRIM 1000003
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
char N[2000001],H[2000001];
long long n,h,v,w,nr[1001];
long long p,k;
int valoare(char A[],int st,int dr)
{
int rez;
rez=0;
for (int i=st;i<=dr;i++)
rez=(rez*26+A[i]-'a')%PRIM; //cu schema lui Horner
return rez;
}
int main()
{
fi>>N+1;
fi>>H+1;
n=strlen(N+1);
h=strlen(H+1);
w=valoare(N,1,n); //valoarea lui needle
v=valoare(H,1,n); //valoarea primei secvente din Haystack
p=1;
for (int i=1;i<=n-1;i++)
p=(p*26)%PRIM; // 26 la puterea n-1
//deoarece prima cifra din baza 26, transf in baza 10 va fi inmultita cu 26 la puterea n-1
for (int i=1;i<=h-n+1;i++)
{
if (v==w)
{
k++;
if( k<=1000)
nr[k]=i;
}
/// trecere cu un caracter spre dreapta
v=(PRIM+v-((H[i]-'a')*p)%PRIM)%PRIM; //scadem prima cifra
v=(v*26+H[i+n]-'a')%PRIM; //adaugam ultima, dupa ce inmultim "partea comuna" cu 26
}
fo<<k<<'\n';
for(int i=1; i<=k && i<=1000; i++)
fo<<nr[i]<<" ";
// fo<<w<<" "<<v;
return 0;
}
//facem trecerea din baza 26 in baza 10
//avem si litere mari si mici, facem altcumva, alta baza