Pagini recente » Cod sursa (job #2427748) | Cod sursa (job #2365532) | Cod sursa (job #1514581) | Cod sursa (job #2076120) | Cod sursa (job #2045404)
#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*58+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*58)%PRIM; // 58 la puterea n-1
//deoarece prima cifra din baza 58, transf in baza 10 va fi inmultita cu 58 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*58+H[i+n]-'A')%PRIM; //adaugam ultima, dupa ce inmultim "partea comuna" cu 58
}
fo<<k<<'\n';
for(int i=1; i<=k && i<=1000; i++)
fo<<nr[i]-1<<" ";
// fo<<w<<" "<<v;
return 0;
}
//facem trecerea din baza 58 in baza 10
//avem si litere mari si mici, facem altcumva, alta baza