Pagini recente » Cod sursa (job #2486928) | Cod sursa (job #195829) | Cod sursa (job #2900092) | Cod sursa (job #2207332) | Cod sursa (job #2794666)
#include <fstream>
#define NHASH 666013 /// numar satanist
#define BHASH 256
#define NMAX 2000000
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
int vsol[NMAX + 1];
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) {
if (ch >= 'A' && ch <= 'Z')
return (current_hash * BHASH + ch - 'A') % NHASH;
return (current_hash * BHASH + ch - 'a') % NHASH;
}
static inline int delete_first_ch(int current_hash, char ch, int pow) {
if (ch >= 'A' && ch <= 'Z')
return (current_hash - (ch - 'A') * pow + NHASH) % NHASH;
return (current_hash - (ch - 'a') * 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);
}
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);
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 < nsol; i++)
cout << vsol[i] << " ";
return 0;
}