Pagini recente » Cod sursa (job #2483175) | Cod sursa (job #2225405) | Cod sursa (job #1437838) | Cod sursa (job #2539952) | Cod sursa (job #1183235)
#include <fstream>
#include <string>
#include <vector>
#include <list>
using namespace std;
ifstream fin("test.in");
ofstream fout("test.out");
#define MAXN 2000001
#define D 123
#define MOD1 100007
#define MOD2 100021
string P, T;
int lgP, lgT;
int hashA1, hashA2, P1, P2;
char match[MAXN], x;
int main(){
fin >> P;
fin.get(x);
fin >> T;
lgP = P.size();
lgT = T.size();
P1 = P2 = 1;
hashA1 = hashA2 = 0;
for (int i = 0; i < lgP; i++){
hashA1 = (hashA1 * D + P[i]) % MOD1;
hashA2 = (hashA2 * D + P[i]) % MOD2;
if (i != 0)
P1 = (P1 * D) % MOD1,
P2 = (P2 * D) % MOD2;
}
if (lgP > lgT){
fout << 0 << '\n';
return 0;
}
int hash1 = 0, hash2 = 0;
for (int i = 0; i < lgP; i++)
hash1 = (hash1 * D + T[i]) % MOD1,
hash2 = (hash2 * D + T[i]) % MOD2;
int Nr = 0;
if (hash1 == hashA1 && hash2 == hashA2)
match[0] = 1, Nr++;
for (int i = lgP; i < lgT; i++){
hash1 = ((hash1 - (T[i - lgP] * P1) % MOD1 + MOD1) * D + T[i]) % MOD1;
hash2 = ((hash2 - (T[i - lgP] * P2) % MOD2 + MOD2) * D + T[i]) % MOD2;
if (hash1 == hashA1 && hash2 == hashA2)
match[i - lgP + 1] = 1,
Nr++;
}
fout << Nr << '\n';
Nr = 0;
for (int i = 0; i < lgT && Nr < 1000; i++)
if (match[i])
Nr++,
fout << i << ' ';
fout << '\n';
return 0;
}