Pagini recente » Cod sursa (job #2562574) | Cod sursa (job #2023371) | Cod sursa (job #2683044) | Cod sursa (job #2775664) | Cod sursa (job #2632448)
#include <fstream>
#include <vector>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
string a, b;
int MOD[2] = {100003, 666013};
int Put[2] = {127, 131};
int Power[2] = {1, 1};
int Val_A[2] = {0, 0};
int Val_B[2] = {0, 0};
int car (char ch) {
return ch - '0';
}
bool Egal (int a[], int b[], int N) {
for (int i = 0; i < N; ++ i ) {
if (a[ i ] != b[ i ]) return false;
}
return true;
}
void Solve () {
if (a.size() > b.size()) {
g << 0 << '\n';
return;
}
for (int i = 0; i < a.size(); ++ i ) {
for (int j = 0; j < 2; ++ j ) {
Val_B[ j ] = (1LL * Val_B[ j ] * Put[ j ] % MOD[ j ] + car(b[ i ])) % MOD[ j ];
Val_A[ j ] = (1LL * Val_A[ j ] * Put[ j ] % MOD[ j ] + car(a[ i ])) % MOD[ j ];
}
}
for (int i = 1; i < a.size(); ++ i ) {
for (int j = 0; j < 2; ++ j ) {
Power[ j ] = (1LL * Power[ j ] * Put[ j ]) % MOD[ j ];
}
}
vector <int> ans;
if (Egal(Val_A, Val_B, 2))
ans.push_back(1);
for (int i = a.size(); i < b.size(); ++ i ) {
for (int j = 0; j < 2; ++ j ) {
Val_B[ j ] = (Val_B[ j ] - 1LL * Power[ j ] * car(b[ i - a.size() ]) % MOD[ j ] + MOD[ j ]) % MOD[ j ];
Val_B[ j ] = (1LL * Val_B[ j ] * Put[ j ] % MOD[ j ] + car(b[ i ])) % MOD[ j ];
}
if (Egal(Val_A, Val_B, 2)) {
ans.push_back(i - a.size() + 1);
}
}
g << ans.size() << '\n';
for (int i = 0; i < min(1000, (int)ans.size()); ++ i ) {
g << ans[ i ] << " ";
}
}
int main()
{
f >> a >> b;
Solve();
return 0;
}