Pagini recente » Cod sursa (job #2277143) | Cod sursa (job #3030786) | Cod sursa (job #455074) | Cod sursa (job #2801849) | Cod sursa (job #1343359)
#include <iostream>
#include <fstream>
#include <cstring>
#define mod1 100007
#define mod2 100021
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string S, P;
int P1, P2, hashA1, hashA2, hash1, hash2, lp, ls;
int sol[1005];
void read() {
fin >> P >> S;
lp = int(P.size());
ls = int(S.size());
}
void solve() {
P1 = P2 = 1;
hashA1 = hashA2 = 0;
for (int i = 0; i < lp; i++)
{
hashA1 = (hashA1 * 26 + P[i]) % mod1;
hashA2 = (hashA2 * 27 + P[i]) % mod2;
if (i != 0)
P1 = (P1 * 26) % mod1,
P2 = (P2 * 27) % mod2;
}
if (lp > ls) {
cout << 0 << "\n";
return;
}
hash1 = hash2 = 0;
for (int i = 0; i < lp; i++) {
hash1 = (hash1 * 26 + S[i]) % mod1;
hash2 = (hash2 * 27 + S[i]) % mod2;
}
int rez = 0;
if (hash1 == hashA1 && hash2 == hashA2) {
sol[++rez] = 1;
}
for (int i = lp; i < ls; i++) {
hash1 = (((hash1 - (S[i - lp] * P1)) % mod1 + mod1) * 26 + S[i]) % mod1;
hash2 = (((hash2 - (S[i - lp] * P2)) % mod2 + mod2) * 27 + S[i]) % mod2;
if (hash1 == hashA1 && hash2 == hashA2) {
++rez;
if (rez <= 1000)
sol[rez] = i - lp + 1;
}
}
fout << rez << "\n";
for (int i = 1; i <= min(1000, rez); i++)
fout << sol[i] << " ";
fout << "\n";
}
int main() {
read();
solve();
fin.close();
fout.close();
return 0;
}