Pagini recente » Cod sursa (job #2966591) | Cod sursa (job #1906030) | Cod sursa (job #438173) | Cod sursa (job #3003022) | Cod sursa (job #1362822)
#include <iostream>
#include <fstream>
#include <cstring>
#define mod1 100007
#define mod2 100021
using namespace std;
string P, S;
int lenS, lenP, pattern1, pattern2, num1, num2, powP1, powP2, k;
int sol[1005];
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> P;
fin >> S;
lenP = int(P.size());
lenS = int(S.size());
if (lenP > lenS) {
fout << 0 << "\n";
return 0;
}
pattern1 = pattern2 = 0;
powP1 = powP2 = 1;
for (int i = 0; i < lenP; i++) {
pattern1 = (pattern1 * 26 + P[i]) % mod1;
pattern2 = (pattern2 * 27 + P[i]) % mod2;
if (i > 0)
powP1 = (powP1 * 26) % mod1,
powP2 = (powP2 * 27) % mod2;
}
num1 = num2 = 0;
for (int i = 0; i < lenP; i++) {
num1 = (num1 * 26 + S[i]) % mod1;
num2 = (num2 * 27 + S[i]) % mod2;
}
k = 0;
if (num1 == pattern1 && num2 == pattern2)
sol[++k] = 0;
for (int i = lenP; i < lenS; i++) {
num1 = (((num1 - (powP1 * S[i - lenP])) % mod1 + mod1) * 26 + S[i]) % mod1;
num2 = (((num2 - (powP2 * S[i - lenP])) % mod2 + mod2) * 27 + S[i]) % mod2;
if (num1 == pattern1 && num2 == pattern2) {
k++;
if (k <= 1000)
sol[k] = i - lenP + 1;
}
}
fout << k << "\n";
for (int i = 1; i <= min(k, 1000); i++)
fout << sol[i] << " ";
fin.close();
fout.close();
return 0;
}