Pagini recente » Cod sursa (job #1326399) | Cod sursa (job #317174) | Cod sursa (job #2166893) | Cod sursa (job #981417) | Cod sursa (job #2792621)
#include <stdio.h>
#include <fstream>
#include <string.h>
#define NMAX 2000000
#define HASH_SIZE 666013
#define HASH_BASE 256
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char str[NMAX + 1];
int strLength;
char pattern[NMAX + 1];
int patternLength;
int rez[NMAX], cnt;
void eraseNewLine(char str[], int& length) {
if (str[length - 1] == '\n')
str[--length] = 0;
}
int lgput(int a, int n, int mod) {
int p;
p = 1;
while (n) {
if (n & 1)
p = (long long)p * a % mod;
a = (long long)a * a % mod;
n >>= 1;
}
return p;
}
bool cmp(char str[], char pattern[]) {
int i;
i = 0;
while (str[i] && pattern[i] && str[i] == pattern[i])
++i;
return pattern[i] == 0;
}
int computeHash(char str[], int length) {
int hash, i;
hash = 0;
i = 0;
while (i < length) {
hash = (hash * HASH_BASE + str[i]) % HASH_SIZE;
++i;
}
return hash;
}
int addToHash(int hash, char ch) {
return (hash * HASH_BASE + ch) % HASH_SIZE;
}
int removeFromHash(int hash, char ch, int power) {
hash -= ch * power % HASH_SIZE;
if (hash < 0)
hash += HASH_SIZE;
return hash;
}
void search(char str[], int strLength, char pattern[], int patternLength) {
int i, patternHash, strHash, power;
bool patternFound;
patternHash = computeHash(pattern, patternLength);
strHash = computeHash(str, patternLength - 1);
//out << patternHash << " " << strHash;
power = lgput(HASH_BASE, patternLength - 1, HASH_SIZE);
i = patternLength;
while (i <= strLength && !patternFound) {
strHash = addToHash(strHash, str[i - 1]);
if (patternHash == strHash && cmp(str + i - patternLength, pattern))
{
cnt++;
rez[cnt] = i - patternLength;
}
strHash = removeFromHash(strHash, str[i - patternLength], power);
++i;
}
}
int main() {
in.getline(pattern, NMAX);
patternLength = strlen(pattern);
eraseNewLine(pattern, patternLength);
in.getline(str, NMAX);
strLength = strlen(str);
eraseNewLine(str, strLength);
search(str, strLength, pattern, patternLength);
out << cnt << '\n';
for (int i = 1; i <= cnt; i++)
out << rez[i] << " ";
return 0;
}