Pagini recente » Cod sursa (job #3268119) | Cod sursa (job #3030956) | Cod sursa (job #2857427) | Cod sursa (job #2987920) | Cod sursa (job #1780788)
#include <fstream>
#include <vector>
#include <cstring>
#define prime 73
#define mod1 100007
#define mod2 100021
#define NMax 2000001
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char x[NMax],y[NMax];
int Hx1,Hy1,Hx2,Hy2,P1,P2,Sx,Sy,ans1;
vector<int> ans;
int main()
{
f.getline(x,NMax);
f.getline(y,NMax);
Sx = strlen(x);
Sy = strlen(y);
P1 = 1;
P2 = 1;
for(int i = 0; i < Sx; ++i){
Hx1 = (Hx1 * prime + x[i]) % mod1;
Hx2 = (Hx2 * prime + x[i]) % mod2;
if(i != 0){
P1 = (P1 * prime) % mod1;
P2 = (P2 * prime) % mod2;
}
}///calculez hashurile substringului
for(int i = 0; i < Sx; ++i){///calculez hashurile primelor Sx litere din text
Hy1 = (Hy1 * prime + y[i]) % mod1;
Hy2 = (Hy2 * prime + y[i]) % mod2;
}
for(int i = 1; i <= Sy - Sx + 1; ++i){
///verific Hy
if(Hy1 == Hx1 && Hy2 == Hx2){
ans1++;
if(ans1 <= 1000)
ans.push_back(i - 1);
}
if(i == Sy) break;
Hy1 = ((Hy1 - (y[i - 1] * P1) % mod1 + mod1) * prime + y[i + Sx - 1]) % mod1;///corectez functiile hasului
Hy2 = ((Hy2 - (y[i - 1] * P2) % mod2 + mod2) * prime + y[i + Sx - 1]) % mod2;///stergand primul element si adaugant ultimul
}
g << ans1 << '\n';
for(int i = 0; i < ans.size(); ++i){
g << ans[i] << ' ';
}
return 0;
}