Pagini recente » Cod sursa (job #2046427) | Cod sursa (job #1255806) | Cod sursa (job #2493325) | Cod sursa (job #131419) | Cod sursa (job #2153190)
#include<fstream>
#include<cstring>
#include<vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAXLEN = 2e6 + 5, ALPHSZ = 75;
const int hashPrime1 = 100007, hashPrime2 = 100021;
char text[MAXLEN], pattern[MAXLEN];
int matches[1005];
int textLen, patternLen, patternHash1, patternHash2, textHash1, textHash2, MaxPwr1, MaxPwr2, matchesLen, matchesCnt;
inline void getHashes(){
int idx;
MaxPwr1 = 1;
MaxPwr2 = 1;
for(idx = 1; idx < patternLen; ++idx){
patternHash1 = ((patternHash1 * ALPHSZ) % hashPrime1 + pattern[idx]) % hashPrime1;
patternHash2 = ((patternHash2 * ALPHSZ) % hashPrime2 + pattern[idx]) % hashPrime2;
textHash1 = ((textHash1 * ALPHSZ) % hashPrime1 + text[idx]) % hashPrime1;
textHash2 = ((textHash2 * ALPHSZ) % hashPrime2 + text[idx]) % hashPrime2;
MaxPwr1 = (MaxPwr1 * ALPHSZ) % hashPrime1;
MaxPwr2 = (MaxPwr2 * ALPHSZ) % hashPrime2;
}
patternHash1 = ((patternHash1 * ALPHSZ) % hashPrime1 + pattern[patternLen]) % hashPrime1;
patternHash2 = ((patternHash2 * ALPHSZ) % hashPrime2 + pattern[patternLen]) % hashPrime2;
textHash1 = ((textHash1 * ALPHSZ) % hashPrime1 + text[patternLen]) % hashPrime1;
textHash2 = ((textHash2 * ALPHSZ) % hashPrime2 + text[patternLen]) % hashPrime2;
}
inline void findMatches(){
int idx;
if(textHash1 == patternHash1 and textHash2 == patternHash2){
++matchesCnt;
matches[++matchesLen] = 0;
}
for(idx = patternLen + 1; idx <= textLen; ++idx){
textHash1 = textHash1 - ((MaxPwr1 * text[idx - patternLen]) % hashPrime1) + hashPrime1;
textHash2 = textHash2 - ((MaxPwr2 * text[idx - patternLen]) % hashPrime2) + hashPrime2;
textHash1 = (textHash1 * ALPHSZ + text[idx]) % hashPrime1;
textHash2 = (textHash2 * ALPHSZ + text[idx]) % hashPrime2;
if(textHash1 == patternHash1 and textHash2 == patternHash2){
++matchesCnt;
if(matchesLen < 1000)
matches[++matchesLen] = idx - patternLen;
}
}
}
inline void printMatches(){
fout << matchesCnt << '\n';
int idx;
for(idx = 1; idx <= matchesLen; ++idx)
fout << matches[idx] << ' ';
}
int main(){
fin >> (pattern + 1) >> (text + 1);
patternLen = strlen(pattern + 1);
textLen = strlen(text + 1);
if(patternLen > textLen){
fout << 0;
return 0;
}
getHashes();
findMatches();
printMatches();
}