Pagini recente » Cod sursa (job #140700) | Borderou de evaluare (job #1200018) | Cod sursa (job #234345) | Cod sursa (job #925186) | Cod sursa (job #3328378)
#include <fstream>
#include <cstring>
#define MOD1 100007
#define MOD2 100021
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char A[2000001], B[2000001];
int poz[2000001];
int main()
{
cin >> A;
cin >> B;
int nrca = strlen(A);
int nrcb = strlen(B);
if(nrca > nrcb){
cout << "0\n";
return 0;
}
int nra1 = 0;
int nra2 = 0;
int nrb1 = 0;
int nrb2 = 0;
int rez = 0;
int p1 = 1;
int p2 = 1;
for(int i = 0; i < nrca; i++){
nra1 = (nra1 * 73 + A[i]) % MOD1;
nra2 = (nra2 * 73 + A[i]) % MOD2;
nrb1 = (nrb1 * 73 + B[i]) % MOD1;
nrb2 = (nrb2 * 73 + B[i]) % MOD2;
}
/*
cout << "nra1 = " << nra1 << "\n";
cout << "nra2 = " << nra2 << "\n";
*/
for(int i = 1; i <= nrca - 1; i++){
p1 = (p1 * 73) % MOD1;
p2 = (p2 * 73) % MOD2;
}
if(nra1 == nrb1 && nra2 == nrb2){
poz[++rez] = 0;
}
for(int i = 0; i <= nrcb - nrca - 1; i++){
nrb1 = ((nrb1 - (B[i] * p1)) % MOD1 + MOD1) % MOD1;
nrb1 = (nrb1 * 73) % MOD1;
nrb1 += B[i + nrca];
nrb1 %= MOD1;
nrb2 = ((nrb2 - (B[i] * p2)) % MOD2 + MOD2) % MOD2;
nrb2 = (nrb2 * 73) % MOD2;
nrb2 += B[i + nrca];
nrb2 %= MOD2;
/*
cout << "nrb1 = " << nrb1 << "\n";
cout << "nrb2 = " << nrb2 << "\n";
*/
if(nra1 == nrb1 && nra2 == nrb2){
poz[++rez] = i+1;
}
}
cout << rez << "\n";
for(int i = 1; i <= rez; i++){
cout << poz[i] << " ";
}
cout << "\n";
return 0;
}