Pagini recente » Cod sursa (job #3183510) | Cod sursa (job #2430137) | Cod sursa (job #2571210) | Cod sursa (job #1289233) | Cod sursa (job #1240351)
#include <fstream>
#include <cstring>
using namespace std;
const int modList[] = {2, 7 + 1e4, 9 + 1e4}, base = 67;
const int N = 1 + 2e6;
char text[N], pattern[N], ind[256];
bool match[N];
inline int getVal(char c){
return ind[c];
}
int pow(int a, int n, int mod){
if (n < 2)
return n == 1 ? a : 1;
return pow(a * a % mod, n >> 1, mod) * pow(a, n & 1, mod) % mod;
}
int eval(char s[], int n, int mod){
int val = 0;
for (int i = 0 ; i < n ; i++)
val = ( val * base + getVal( s[i] ) ) % mod;
return val;
}
void rabinKarp(char text[], char pattern[], int mod){
int n = strlen(pattern);
int desiredVal = eval(pattern, n, mod), val = eval(text, n, mod), p = pow(base, n, mod);
for (int i = 0 ; text[i] ; i++){
if (desiredVal != val)
match[i] = false;
val = (val * base % mod + getVal( text[i + n] ) - getVal( text[i] ) * p % mod + mod ) % mod;
}
}
void patternMatch(char text[], char pattern[]){
memset(ind, 0, sizeof(ind));
int nr = 0;
for (char c = 'a' ; c <= 'z' ; c++)
ind[c] = nr++;
for (char c = 'A' ; c <= 'Z' ; c++)
ind[c] = nr++;
for (char c = '0' ; c <= '9' ; c++)
ind[c] = nr++;
memset(match, true, sizeof(match));
for (int i = 1 ; i <= modList[0] ; i++)
rabinKarp(text, pattern, modList[i]);
}
int main(){
ifstream in("strmatch.in");
in >> pattern >> text;
in.close();
patternMatch(text, pattern);
ofstream out("strmatch.out");
int cntHits = 0;
for (int i = 0 ; text[i] ; i++)
if ( match[i] )
cntHits++;
out << cntHits << '\n';
if (1000 < cntHits)
cntHits = 1000;
for (int i = 0 ; cntHits ; i++)
if ( match[i] ){
out << i << ' ';
cntHits--;
}
out << '\n';
out.close();
return 0;
}