Pagini recente » Cod sursa (job #54110) | Cod sursa (job #2141375) | Cod sursa (job #1895348) | Cod sursa (job #586898) | Cod sursa (job #2765711)
#include <iostream>
#include <fstream>
#include <vector>
#define MOD 20000009
#define hashVal 63
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n1, n2, count = 0;
vector<int> ans;
int getVal(char c) {
if (c >= 'a' && c <= 'z') {
return c - 'a' + 1;
} else if (c >= 'A' && c <= 'Z') {
return c - 'A' + 27;
}
return c - '0' + 53;
}
int main() {
string s1, s2;
f >> s2 >> s1;
n1 = s1.length();
n2 = s2.length();
int lastHashFactor = hashVal;
for (int i = 2; i < n2; i++)
lastHashFactor = lastHashFactor * hashVal % MOD;
if (n1 < n2) {
g << 0;
return 0;
}
int hashFactor = lastHashFactor;
int stringB_hashVal = 0;
for (int i = 0; i < n2; i++) {
int val = getVal(s2[i]);
stringB_hashVal = (stringB_hashVal + val * hashFactor) % MOD;
hashFactor /= 63;
}
hashFactor = lastHashFactor;
int stringA_hashVal = 0;
for (int i = 0; i < n2; i++) {
int val = getVal(s1[i]);
stringA_hashVal = (stringA_hashVal + val * hashFactor) % MOD;
//cout << s1[i] << " " << stringA_hashVal << " " << hashFactor << "\n";
hashFactor /= 63;
}
if (stringA_hashVal == stringB_hashVal) {
count++;
ans.push_back(0);
}
for (int i = n2; i < n1; i++) {
hashFactor = lastHashFactor;
int prevVal = getVal(s1[i-n2]);
int val = getVal(s1[i]);
int newPos = stringA_hashVal - (prevVal * hashFactor) % MOD;
if (newPos < 0)
newPos *= -1;
stringA_hashVal = ((newPos % MOD) * hashVal) % MOD;
stringA_hashVal = (stringA_hashVal + val) % MOD;
if (stringB_hashVal == stringA_hashVal) {
count++;
if (count < 1000)
ans.push_back(i - n2 + 1);
}
}
g << count << "\n";
for (int i = 0; i < ans.size(); i++)
g << ans[i] << " ";
return 0;
}