Pagini recente » Cod sursa (job #1064273) | Cod sursa (job #1987861) | Cod sursa (job #1767391) | Cod sursa (job #2469378) | Cod sursa (job #1251517)
#include<iostream>
#include<fstream>
#include<vector>
#include<string.h>
using namespace std;
#define MAXN 2000001
#define MOD1 10007
#define MOD2 666013
#define PRIME1 27
#define PRIME2 29
int hashA1, hashA2;
int P1, P2;
char A[MAXN], B[MAXN];
void read(){
ifstream fin("strmatch.in");
fin.getline(A, MAXN);
fin.getline(B, MAXN);
fin.close();
}
void solve(){
int v1 = 0;
int v2 = 0;
int NA = strlen(A);
int NB = strlen(B);
ofstream fout("strmatch.out");
if (NA > NB)
{
fout << "0\n";
return;
}
int P1 = 1, P2 = 1;
for (int i = 0; i < NA; i++)
{
v1 = (v1 * PRIME1 + A[i]) % MOD1;
v2 = (v2 * PRIME2 + A[i]) % MOD2;
if (i != 0){
P1 = (P1 * PRIME1) % MOD1;
P2 = (P2 * PRIME2) % MOD2;
}
}
//hasurile pentru A au fost facute
int h1 = 0, h2 = 0;
vector<int> poz;
int cate = 0;
for (int i = 0; i < NA; i++)
{
h1 = (h1 * PRIME1 + B[i]) % MOD1;
h2 = (h2 * PRIME2 + B[i]) % MOD2;
}
if (h1 == v1 && h2 == v2){
cate++;
poz.push_back(0);
}
for (int i = NA; i < NB; i++){
h1 = ((h1 - (B[i - NA] * P1) % MOD1 + MOD1) * PRIME1 + B[i]) % MOD1;
h2 = ((h2 - (B[i - NA] * P2) % MOD2 + MOD2) * PRIME2 + B[i]) % MOD2;
if (h1 == v1 && h2 == v2){
cate++;
poz.push_back(i);
}
}
fout << cate << "\n";
int NV = poz.size();
for (int i = 0; i < NV; i++){
fout << poz[i] << " ";
}
}
int main(){
read();
solve();
return 0;
}