Pagini recente » Cod sursa (job #3240422) | Cod sursa (job #623303) | Cod sursa (job #2459453) | Cod sursa (job #2717322) | Cod sursa (job #2388344)
#include <bits/stdc++.h>
using namespace std;
string text;
string pattern;
const int base = 256;
const int prime = 101;
int computeHash(string text, int length){
int hash = 0;
for (int index = 0; index < length; index++){
hash *= 256;
int letter = text[index];
hash += letter;
hash %= prime;
}
if (hash < 0)
hash += prime;
return hash;
}
const long long offSet = (((base%prime)*base)%prime);
int nextHash(long long hash, int newPos, string text, int length){
int oldPos = newPos-length;
hash += prime;
hash -= text[oldPos]*offSet;
hash *= base;
hash += text[newPos];
hash %= prime;
if (hash < 0)
hash += prime;
return hash;
}
vector <int> matches;
bool checkMatch(string text, string pattern, int pos){
for (int i = 0; i < pattern.size(); i++){
if (text[i+pos] != pattern[i])
return false;
}
return true;
}
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main() {
fin >> pattern;
fin >> text;
int patternHash = computeHash(pattern, pattern.size());
int currentHash = computeHash(text, pattern.size());
if (patternHash == currentHash)
if (checkMatch(text, pattern, 0))
matches.push_back(0);
for (int index = pattern.size(); index < text.size(); index++){
currentHash = nextHash(currentHash, index, text, pattern.size());
if (patternHash == currentHash){
int start = index-pattern.size()+1;
if (checkMatch(text, pattern, start))
matches.push_back(start);
}
}
fout << matches.size() << "\n";
int index = 0;
for (auto it : matches){
fout << it << " ";
if (index == 1000)
break;
}
}