Pagini recente » Cod sursa (job #3164930) | Cod sursa (job #240430) | Cod sursa (job #2548483) | Cod sursa (job #186482) | Cod sursa (job #2794680)
#include <fstream>
#include <map>
#define NHASH 666013 /// numar satanist
#define BHASH 256
#define NMAX 2000000
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
map<char, int> mpval;
int vsol[NMAX + 1];
static inline int minim(int a, int b) {
return a < b ? a : b;
}
int lgput(int base, int exp) {
int sol;
if (exp == 0)
return 1;
sol = lgput(base, exp / 2);
sol = (sol * sol) % NHASH;
if (exp % 2 == 1)
sol = (sol * base) % NHASH;
return sol;
}
static inline int add_ch(int current_hash, char ch) {
return (current_hash * BHASH + mpval[ch]) % NHASH;
}
static inline int delete_first_ch(int current_hash, char ch, int pow) {
return (current_hash - mpval[ch] * pow + NHASH) % NHASH;
}
bool strcmp(string& A, string& B, int pozsta) {
int i, nb;
nb = B.size();
i = 0;
while (i < nb && A[i + pozsta] == B[i])
i++;
return (i == nb);
}
void prec_mp() {
char ch;
for (ch = 'a'; ch <= 'z'; ch++)
mpval[ch] = ch - 'a';
for (ch = 'A'; ch <= 'Z'; ch++)
mpval[ch] = ch - 'A' + 'z' - 'a' + 1;
for (ch = '0'; ch <= '9'; ch++)
mpval[ch] = ch - '0' + 'Z' - 'A' + 'z' - 'a' + 2;
}
int main() {
int pow, pattern_hash, current_hash, ns, np, i, nsol;
string pattern, s;
cin >> pattern >> s;
ns = s.size();
np = pattern.size();
pow = lgput(BHASH, np);
prec_mp();
pattern_hash = 0;
for (i = 0; i < np; i++)
pattern_hash = add_ch(pattern_hash, pattern[i]);
current_hash = nsol = 0;
for (i = 0; i < ns; i++) {
current_hash = add_ch(current_hash, s[i]);
if (i >= np) {
current_hash = delete_first_ch(current_hash, s[i - np], pow);
if (current_hash == pattern_hash && strcmp(s, pattern, i - np + 1))
vsol[nsol++] = i - np + 1;
}
}
cout << nsol << "\n";
for (i = 0; i < minim(1000, nsol); i++)
cout << vsol[i] << " ";
return 0;
}