Pagini recente » Cod sursa (job #2794840) | Cod sursa (job #2794738) | Cod sursa (job #2346826) | Cod sursa (job #2794742) | Cod sursa (job #2794731)
#include <fstream>
#include <vector>
#include <map>
#define NHASH 666013 /// numar satanist
#define BHASH 63
#define NMAX 2000000
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
vector <int> vsol;
map<char, int> mpval;
int add_ch(int current_hash, char ch, int base, int MOD) {
return ((current_hash * base) % MOD + mpval[ch]) % MOD;
}
int del_ch(int current_hash, char ch, int pow, int MOD) {
return (current_hash - (mpval[ch] * pow) % MOD + MOD) % MOD;
}
void prec_mpval() {
int cnt = 0;
char ch;
for (ch = 'a'; ch <= 'z'; ch++)
mpval[ch] = cnt++;
for (ch = 'A'; ch <= 'Z'; ch++)
mpval[ch] = cnt++;
for (ch = '0'; ch <= '9'; ch++)
mpval[ch] = cnt++;
}
int prec_pow(int base, int exp, int MOD) {
int i, pow;
pow = 1;
for (i = 0; i < exp; i++)
pow = (pow * base) % MOD;
return pow;
}
bool strcmp(string& A, int pozsta, int pozdra, string& B) {
int nb, i;
nb = B.size();
if (nb != pozdra - pozsta + 1)
return 0;
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();
prec_mpval();
pow = prec_pow(BHASH, np - 1, NHASH);
pattern_hash = 0;
current_hash = 0;
for (i = 0; i < np; i++) {
pattern_hash = add_ch(pattern_hash, pattern[i], BHASH, NHASH);
current_hash = add_ch(current_hash, s[i], BHASH, NHASH);
}
if (current_hash == pattern_hash && strcmp(s, 0, np - 1, pattern))
vsol.push_back(0);
for (i = np; i < ns; i++) {
current_hash = add_ch(del_ch(current_hash, s[i - np], pow, NHASH), s[i], BHASH, NHASH);
if (current_hash == pattern_hash && strcmp(s, i - np + 1, i, pattern))
vsol.push_back(i - np + 1);
}
cout << vsol.size() << "\n";
for (i = 0; i < vsol.size() && i < 1000; i++)
cout << vsol[i] << " ";
return 0;
}