Pagini recente » Cod sursa (job #3225322) | Cod sursa (job #3295605) | Cod sursa (job #3292996) | Cod sursa (job #3281813) | Cod sursa (job #2388335)
#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 = 1; index <= text.size()-pattern.size(); index++){
currentHash = nextHash(currentHash, index+pattern.size()-1, text, pattern.size());
if (patternHash == currentHash){
if (checkMatch(text, pattern, index))
matches.push_back(index);
}
}
fout << matches.size() << "\n";
int index = 0;
for (auto it : matches){
fout << it << " ";
if (index == 1000)
break;
}
}