Pagini recente » Cod sursa (job #1957666) | Cod sursa (job #3205039) | Cod sursa (job #1265411) | Cod sursa (job #1550937) | Cod sursa (job #2755386)
#include<iostream>
#include<fstream>
#include<cstring>
#include<vector>
#define N 2000002
#define NR_POZ 1000
using namespace std;
int nr;
int poz[NR_POZ];
int pi[N];
char s[N],t[N];
void rabin_karp(char *s, char *t) {
int p = 31;
int m = 1e9 + 9;
int ns = strlen(s), nt = strlen(t);
vector<long long> p_pow(max(ns, nt));
p_pow[0] = 1;
for (int i = 1; i < p_pow.size(); i++) {
p_pow[i] = (p_pow[i-1] * p) % m;
}
vector<int> hash_t(nt + 1, 0);
for (int i = 0; i < nt; i++)
if(t[i]<='Z' && t[i]>='A')
hash_t[i+1] = (hash_t[i] + (t[i] - 'A' + 1) * p_pow[i]) % m;
else
if(t[i]<='z' && t[i]>='a')
hash_t[i+1] = (hash_t[i] + (t[i] - 'a' + 1) * p_pow[i]) % m;
else
hash_t[i+1] = (hash_t[i] + (t[i] - '0' + 1) * p_pow[i]) % m;
int hash_s = 0;
for (int i = 0; i < ns; i++) {
if(s[i]<='Z' && s[i]>='A')
hash_s = (hash_s + (s[i] - 'A' + 1) * p_pow[i]) % m;
else
if(s[i]<='z' && s[i]>='a')
hash_s = (hash_s + (s[i] - 'a' + 1) * p_pow[i]) % m;
else
hash_s = (hash_s + (s[i] - '0' + 1) * p_pow[i]) % m;
}
for (int i = 0; i + ns - 1 < nt; i++) {
int cur_h = (hash_t[i+ns] + m - hash_t[i]) % m;
if (cur_h == hash_s * p_pow[i] % m){
poz[nr]=i;
nr++;
}
}
}
int main(){
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>s>>t;
rabin_karp(s,t);
g<<nr<<endl;
for(int i=0;i<min(NR_POZ,nr);i++)
g<<poz[i]<<" ";
g.close();
}