Pagini recente » Cod sursa (job #2108980) | Cod sursa (job #1210199) | Cod sursa (job #2046313) | Cod sursa (job #2743600) | Cod sursa (job #2632458)
#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};
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 ] + b[ i ] - '0') % MOD[ j ];
Val_A[ j ] = (1LL * Val_A[ j ] * Put[ j ] % MOD[ j ] + a[ i ] - '0') % MOD[ j ];
if (i != a.size() - 1) Power[ j ] = (1LL * Power[ j ] * Put[ j ]) % MOD[ j ];
}
}
vector <int> ans;
if (Val_A[ 0 ] == Val_B[ 0 ] && Val_A[ 1 ] == Val_B[ 1 ])
ans.push_back(0);
for (int i = a.size(); i < b.size(); ++ i ) {
for (int j = 0; j < 2; ++ j ) {
Val_B[ j ] = ((Val_B[ j ] - ((b[ i - a.size() ] - '0') * Power[ j ]) % MOD[ j ] + MOD[ j ]) * Put[ j ] + (b[ i ] - '0')) % MOD[ j ];
}
if (Val_A[ 0 ] == Val_B[ 0 ] && Val_A[ 1 ] == Val_B[ 1 ]) {
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;
}