Pagini recente » Cod sursa (job #2759418) | Cod sursa (job #462610) | Cod sursa (job #3036667) | Cod sursa (job #2975610) | Cod sursa (job #1904671)
#include <fstream>
#include <vector>
#include <string>
using namespace std;
inline void fasterLLDivMod(unsigned long long x, unsigned y, unsigned &out_d, unsigned &out_m) {
unsigned xh = (unsigned)(x >> 32), xl = (unsigned)x, d, m;
#ifdef __GNUC__
asm(
"divl %4; \n\t"
: "=a" (d), "=d" (m)
: "d" (xh), "a" (xl), "r" (y)
);
#else
__asm {
mov edx, dword ptr[xh];
mov eax, dword ptr[xl];
div dword ptr[y];
mov dword ptr[d], eax;
mov dword ptr[m], edx;
};
#endif
out_d = d; out_m = m;
}
//x / y < 2^32 !
inline unsigned fasterLLMod(unsigned long long x, unsigned y) {
unsigned dummy, r;
fasterLLDivMod(x, y, dummy, r);
return r;
}
const int MOD1 = 1000000000 + 7;
const int C1 = 257;
const int MOD2 = 1000000000 + 9;
const int C2 = 263;
int N, M;
string A, B;
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin >> A >> B;
N = A.size();
M = B.size();
if (N > M) {
cout << "0\n";
return 0;
}
A = " " + A;
B = " " + B;
int h1A = 0;
int h2A = 0;
int C1N = 1;
int C2N = 1;
for (int i = 1; i <= N; ++ i) {
h1A = fasterLLMod((1LL * h1A * C1 + A[i]), MOD1);
h2A = fasterLLMod((1LL * h2A * C2 + A[i]), MOD2);
C1N = fasterLLMod((1LL * C1N * C1), MOD1);
C2N = fasterLLMod((1LL * C2N * C2), MOD2);
}
vector <int> sol;
int h1B = 0;
int h2B = 0;
for (int i = 1; i <= M; ++ i) {
h1B = fasterLLMod((1LL * h1B * C1 + B[i]), MOD1);
h2B = fasterLLMod((1LL * h2B * C2 + B[i]), MOD2);
if (i >= N + 1) {
h1B = (h1B - fasterLLMod(1LL * B[i - N] * C1N, MOD1));
if (h1B < 0)
h1B += MOD1;
h2B = (h2B - fasterLLMod(1LL * B[i - N] * C2N, MOD2));
if (h2B < 0)
h2B += MOD2;
}
if (i >= N && h1A == h1B && h2A == h2B)
sol.push_back(i - N);
}
cout << sol.size() << '\n';
if (sol.empty())
cout << '\n';
else {
cout << sol[0];
for (int i = 1; i < 1000 && i < sol.size(); ++ i)
cout << ' ' << sol[i];
cout << '\n';
}
return 0;
}