Pagini recente » Cod sursa (job #378934) | Cod sursa (job #2761231) | Cod sursa (job #562155) | Cod sursa (job #336946) | Cod sursa (job #2380562)
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define NMax 2000010
#define b 256
#define Mod 100003
#define Mod2 100019
int d1;
string A, B;
int m, n;
int hashA1;
int hash1;
vector<int> poz;
bool IsPrim(int x){
int i;
int sq = sqrt(x);
if(x % 2 == 0) return 0;
for(i = 3; i <= sq; i++)
if(x % i == 0) return 0;
return 1;
}
void RK();
bool verifica(int);
int main(){
fin >> A >> B;
RK();
}
void RK(){
int i, k;
m = A.size();
n = B.size();
d1 = (int)pow(b, m-1) % Mod;
for(i = 0; i < m; i++){
hashA1 = (hashA1 * b + A[i]) % Mod;
hash1 = (hash1 * b + B[i]) % Mod;
}
if(hashA1 == hash1 && verifica(0)) poz.push_back(0);
for(k = 0; k < n - m; k++){
hash1 = (hash1 + b * Mod - d1 * B[k]) % Mod;
hash1 = (hash1 * b + B[k + m]) % Mod;
if(hashA1 == hash1 && verifica(k + 1)) poz.push_back(k + 1);
}
fout << poz.size() << '\n';
for(i = 0; i < poz.size(); i++) fout << poz[i] << ' ';
}
bool verifica(int x){
for(int i = 0; i < m; i++) if(A[i] != B[i + x]) return 0;
return 1;
}