Pagini recente » Cod sursa (job #569839) | Cod sursa (job #1856988) | Cod sursa (job #1494640) | Cod sursa (job #652889) | Cod sursa (job #2632461)
#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;
}
Val_B[ 0 ] = Val_B[ 1 ] = b[ 0 ] - '0';
Val_A[ 0 ] = Val_A[ 1 ] = a[ 0 ] - '0';
for (int i = 1; i < a.size(); ++ i ) {
for (int j = 0; j < 2; ++ j ) {
Val_B[ j ] = (Val_B[ j ] * Put[ j ] % MOD[ j ] + b[ i ] - '0') % MOD[ j ];
Val_A[ j ] = (Val_A[ j ] * Put[ j ] % MOD[ j ] + a[ i ] - '0') % MOD[ j ];
Power[ j ] = (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;
}