Pagini recente » Cod sursa (job #2132190) | Cod sursa (job #66779) | Cod sursa (job #149343) | Cod sursa (job #2633212) | Cod sursa (job #2137937)
#include <fstream>
#include <vector>
#include <cstring>
#define MOD1 100007
#define MOD2 100021
using namespace std;
const int b = 73;
const int N = 2000006;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int h1,h2;
int hb1[N];
int hb2[N];
char sir[N];
int p1,p2,m,n;
int v[1005];
int main()
{
f>>sir;
n = strlen(sir);
p1 = 1;
p2 = 1;
for(int i = 0; i< n; i++){
h1 = (h1*b%MOD1+sir[i])%MOD1;
h2 = (h2*b%MOD2+sir[i])%MOD2;
if(i!=0){
p1 = (p1*b)%MOD1;
p2 = (p2*b)%MOD2;
}
}
//g<<h1<<" "<<h2<<"\n\n";
f>>sir;
m = strlen(sir);
hb1[0] = sir[0] % MOD1;
hb2[0] = sir[0] % MOD2;
for(int i = 1; i< n; i++){
hb1[i] = (hb1[i-1] * b % MOD1 + sir[i]) % MOD1;
hb2[i] = (hb2[i-1] * b % MOD2 + sir[i]) % MOD2;
}
int ht1,ht2,nr = 0;
ht1 = hb1[n-1];
ht2 = hb2[n-1];
if(hb1[n-1]==h1 && hb2[n-1]==h2){
nr++;
v[nr] = 0;
}
for(int i = n; i< m; i++){
//ht1 = (hb1[i]-hb1[i-n]*p1%MOD1+MOD1)%MOD1;
//ht2 = (hb2[i]-hb2[i-n]*p2%MOD2+MOD2)%MOD2;
ht1 = ((ht1 - sir[i-n]*p1%MOD1+MOD1)%MOD1*b+sir[i])%MOD1;
ht2 = ((ht2 - sir[i-n]*p2%MOD2+MOD2)%MOD2*b+sir[i])%MOD2;
//g<<i-n<<" "<<i<<" "<<ht1<<" "<<ht2<<"\n";
if(ht1 == h1 && ht2 == h2){
nr++;
if(nr<=1000)
v[nr] = i-n+1;
}
}
g<<nr<<"\n";
for(int i =1; i<=nr&&i<=1000;i++){
g<<v[i]<<" ";
}
f.close();
g.close();
return 0;
}