Pagini recente » Cod sursa (job #63213) | Cod sursa (job #1475853) | Cod sursa (job #626871) | Cod sursa (job #1961349) | Cod sursa (job #2196525)
#include <fstream>
#include <vector>
#include <cstring>
#include <cctype>
#define MOD1 666013
#define MOD2 10013
#define BAZA1 127
#define BAZA2 131
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[2000005];
char B[2000005];
long long n, m;
int i,j;
long long h1, h2;
long long h11, h22;
long long putere1, putere2;
vector <long long> SOL;
long long lgput (long long n, long long p, long long mod)
{
long long sol=1;
long long aux=n;
int i;
for(i=0; (1<<i)<=p; ++i) {
if((p&(1<<i))!=0)
sol=(sol*aux)%mod;
aux=(aux*aux)%mod;
}
return sol;
}
int main()
{
f.getline(A, 2000002);
f.getline(B, 2000002);
n=strlen(A);
m=strlen(B);
h1=h2=0;
h11=h22=0;
for(i=0; i<n; i++) {
h1=(h1*BAZA1%MOD1 + (A[i]-'0'))%MOD1;
h2=(h2*BAZA2%MOD2 + (A[i]-'0'))%MOD2;
h11=(h11*BAZA1%MOD1 + (B[i]-'0'))%MOD1;
h22=(h22*BAZA2%MOD2 + (B[i]-'0'))%MOD2;
}
putere1=lgput(BAZA1, n-1, MOD1);
putere2=lgput(BAZA2, n-1, MOD2);
if(h1==h11 && h2==h22)
SOL.push_back(0);
for(i=n; i<m; i++) {
h11=((h11-((B[i-n]-'0')*putere1)%MOD1+MOD1)*BAZA1+(B[i]-'0'))%MOD1;
h22=((h22-((B[i-n]-'0')*putere2)%MOD2+MOD2)*BAZA2+(B[i]-'0'))%MOD2;
if(h1==h11 && h2==h22)
SOL.push_back(i-n+1);
}
g<<SOL.size()<<'\n';
for(i=0; i<1000 && i<SOL.size(); i++)
g<<SOL[i]<<' ';
g<<'\n';
return 0;
}