Pagini recente » Cod sursa (job #225713) | Cod sursa (job #3189857) | Cod sursa (job #1805073) | Cod sursa (job #3270388) | Cod sursa (job #1200362)
#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 MOD = 100021, p = 80;
long long hashA = 0, h = 0;
for(int i=0; i<n; i++){
hashA = (p*hashA + A[i]) % MOD;
h = (p*h + B[i]) % MOD;
}
long long p1 = p % MOD;
for(int i=2; i<= n; i++){ p1 = (p*p1) % MOD; }
vector <int> V;
if(hashA == h){ V.push_back(0); }
for(int i=1; i<=m-n; i++){
h = ( (p*h)%MOD - (B[i-1]*p1)%MOD + MOD +B[i+n-1]%MOD )%MOD;
if(hashA == h) 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] << " ";
}