Pagini recente » Cod sursa (job #2920839) | Cod sursa (job #3200583) | Cod sursa (job #841477) | Cod sursa (job #384910) | Cod sursa (job #1200366)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
int main(){
string A, B;
ifstream inFile("strmatch.in");
ofstream outFile("strmatch.out");
inFile >> A;
inFile >> B;
long long n = A.size(), m = B.size();
// outFile << A << "\n" << B << "\n" << n << " " << m;
long long MOD1 = 100021, p = 80;
long long hashA1 = 0, h1 = 0;
long long MOD2 = 100007;
long long hashA2 = 0, h2 = 0;
for(int i=0; i<n; i++){
hashA1 = (p*hashA1 + A[i]) % MOD1;
h1 = (p*h1 + B[i]) % MOD1;
hashA2 = (p*hashA2 + A[i]) % MOD2;
h2 = (p*h2 + B[i]) % MOD2;
}
long long p1 = p % MOD1, p2 = p % MOD2;
for(int i=2; i<= n; i++){ p1 = (p*p1) % MOD1; p2=(p*p2)%MOD2; }
vector <int> V;
if( (hashA1 == h1)&&(hashA2==h2) ){ V.push_back(0); }
for(int i=1; i<=m-n; i++){
h1 = ( (p*h1)%MOD1 - (B[i-1]*p1)%MOD1 + MOD1 +B[i+n-1]%MOD1 )%MOD1;
h2 = ( (p*h2)%MOD2 - (B[i-1]*p2)%MOD2 + MOD2 +B[i+n-1]%MOD2 )%MOD2;
if( (hashA1 == h1)&&(hashA2==h2) ) V.push_back(i);
}
int l = (V.size()<1000)?V.size():1000;
// outFile << "\n";
outFile << V.size() << "\n";
for(int i=0; i<l; i++) outFile << V[i] << " ";
}