Pagini recente » Cod sursa (job #2774315) | Cod sursa (job #498197) | Cod sursa (job #1871541) | Cod sursa (job #3218303) | Cod sursa (job #1956718)
#include <fstream>
#include <string.h>
#define mod1 100007
#define mod2 100021
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char A[2000001];
char B[2000001];
int afis[1002];
int main (){
int P = 73;
int P1 = 1;
int P2 = 1;
fin >> A >> B;
int lgA = strlen(A);
int lgB = strlen(B);
// Hash pentru sirul pe care il cautam
int hashA1 = 0;
int hashA2 = 0;
if (lgA > lgB){
fout << "0\n";
return 0;
}
for (int i = 0; i < lgA; ++i){
hashA1 = (hashA1*P+A[i])%mod1;
hashA2 = (hashA2*P+A[i])%mod2;
// codificarea in baza P pt ambele hashuri
if (i!=0){
P1 = (P1*P) % mod1;
P2 = (P2*P) % mod2;
}
// Puterea la care se ajunge pt cele 2 hashuri
}
// ABA = 26^2*A + 26*B + A
int hashB1 = 0;
int hashB2 = 0;
for (int i = 0 ; i < lgA; ++i){
hashB1 = (hashB1*P+B[i])%mod1;
hashB2 = (hashB2*P+B[i])%mod2;
}
int poz = 0;
if (hashA1 == hashB1 && hashA2 == hashB2)
afis[++poz] = 0;
for (int i = 1; i <= lgB - lgA; ++i){
hashB1 = ((hashB1 - (B[i-1] * P1)%mod1 + mod1) * P + B[i+lgA-1])%mod1;
hashB2 = ((hashB2 - (B[i-1] * P2)%mod2 + mod2) * P + B[i+lgA-1])%mod2;
if (hashA1 == hashB1 && hashA2 == hashB2)
afis[++poz] = i;
}
fout << poz << "\n";
int cnt = 0;
for (int i = 1; i <= poz && cnt < 1000; ++i){
fout << afis[i] << " ";
cnt++;
}
}