Pagini recente » Concursuri Virtuale | Cod sursa (job #1240349)
#include <fstream>
#include <cstring>
using namespace std;
const int modList[] = {2, 7 + 1e9, 9 + 1e9}, base = 57;
const int N = 1 + 2e6;
char text[N], pattern[N];
bool match[N];
inline int getVal(char c){
return c <= 'Z' ? c - 'A' : c - 'a' + 27;
}
long long pow(long long 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){
long long 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);
long long desiredVal = eval(pattern, n, mod), val = eval(text, n, mod), p = pow(base, n, mod);
for (int i = 0 ; text[i + n - 1] ; i++){
if (desiredVal != val)
match[i] = false;
val = ( (val * base + getVal( text[i + n] ) - getVal( text[i] ) * p) % mod + mod ) % mod;
}
}
void patternMatch(char text[], char pattern[]){
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, len = strlen(pattern) - 1;
for (int i = 0 ; text[i + len] ; 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;
}