Pagini recente » Cod sursa (job #2971471) | Cod sursa (job #1452302) | Cod sursa (job #2435951) | Cod sursa (job #1873174) | Cod sursa (job #2153106)
#include<fstream>
#include<cstring>
#include<ctime>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAXLEN = 2e6 + 5, ALPHSZ = 73;
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 getMaxPwr(){
MaxPwr1 = 1;
MaxPwr2 = 1;
int exponent;
for(exponent = 1; exponent < patternLen; ++exponent){
MaxPwr1 = (1ULL * MaxPwr1 * ALPHSZ) % hashPrime1;
MaxPwr2 = (1ULL * MaxPwr2 * ALPHSZ) % hashPrime2;
}
}
inline void getPatternHashes(){
int idx;
for(idx = 1; idx <= patternLen; ++idx){
patternHash1 = ((1ULL * patternHash1 * ALPHSZ) % hashPrime1 + pattern[idx]) % hashPrime1;
patternHash2 = ((1ULL * patternHash2 * ALPHSZ) % hashPrime2 + pattern[idx]) % hashPrime2;
}
}
inline void getTextHashes(){
int idx;
for(idx = 1; idx < patternLen; ++idx){
textHash1 = ((1ULL * textHash1 * ALPHSZ) % hashPrime1 + text[idx]) % hashPrime1;
textHash2 = ((1ULL * textHash2 * ALPHSZ) % hashPrime2 + text[idx]) % hashPrime2;
}
}
inline void findMatches(){
int idx;
for(idx = patternLen; idx <= textLen; ++idx){
textHash1 = ((1ULL * textHash1 * ALPHSZ) % hashPrime1 + text[idx]) % hashPrime1;
textHash2 = ((1ULL * textHash2 * ALPHSZ) % hashPrime2 + text[idx]) % hashPrime2;
if(textHash1 == patternHash1 and textHash2 == patternHash2){
++matchesCnt;
if(matchesLen < 1000)
matches[++matchesLen] = idx - patternLen;
}
textHash1 = textHash1 - ((1ULL * MaxPwr1 * text[idx - patternLen + 1]) % hashPrime1) + hashPrime1;
textHash2 = textHash2 - ((1ULL * MaxPwr2 * text[idx - patternLen + 1]) % hashPrime2) + hashPrime2;
}
}
inline void printMatches(){
int idx;
fout << matchesCnt << '\n';
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;
}
getMaxPwr();
getPatternHashes();
getTextHashes();
findMatches();
printMatches();
}