Pagini recente » Cod sursa (job #3257521) | Cod sursa (job #390181) | Cod sursa (job #2560368) | Cod sursa (job #401310) | Cod sursa (job #2723584)
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
long long hashValue[2000005];
long long v[2000005];
long long multiplier[20000005];
long long MOD = 1999999973;
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string pattern, text;
fin >> pattern >> text;
long long n, m, sumPattern = 0, r = 1000, k = 0, cnt = 0;
n = text.size();
m = pattern.size();
multiplier[0] = 1;
for (int i = 1; i < m; ++i) {
multiplier[i] = ((r % MOD) * multiplier[i - 1]) % MOD;
}
for (int i = 0; i < m; ++i) {
char y = pattern.at(i);
char x = text.at(i);
sumPattern += (((int(y))% MOD) * multiplier[m - i - 1]) % MOD;
k += (((int(x))% MOD) * multiplier[m - i - 1]) % MOD;
}
hashValue[0] = k;
for (int i = 0; i < n; ++i) {
char x = text.at(i);
v[i] = int(x);
}
for (int i = 1; i < n - m + 1; ++i) {
hashValue[i] = ((hashValue[i - 1] - ((v[i - 1] % MOD) * multiplier[m - 1]) % MOD) * 1000) % MOD + v[i+m-1] % MOD;
hashValue[i] += MOD;
hashValue[i] %= MOD;
}
for (int i = 0; i < n - m + 1; ++i) {
int y = 0, z;
if(sumPattern == hashValue[i]) {
z = i;
while(pattern[y] == text[z]) {
y += 1;
z += 1;
}
if (y == pattern.size()) {
cnt += 1;
}
}
}
fout << cnt << "\n";
cnt = 0;
for (int i = 0; i < n - m + 1; ++i) {
int y = 0, z;
if(sumPattern == hashValue[i]) {
z = i;
while(pattern[y] == text[z]) {
y += 1;
z += 1;
}
if (y == pattern.size() && cnt < 1000) {
cnt += 1;
fout << i << " ";
}
}
}
return 0;
}