Pagini recente » Cod sursa (job #1196447) | Cod sursa (job #43049) | Cod sursa (job #2664844) | Cod sursa (job #69931) | Cod sursa (job #899183)
Cod sursa(job #899183)
#include <fstream>
#include <string>
#include <vector>
#define B1 29
#define B2 31
#define B3 37
#define mod 999983
using namespace std;
ifstream cin;
ofstream cout;
vector < int > sol;
string a, b;
int main()
{
cin.open("strmatch.in");
cout.open("strmatch.out");
getline(cin, a);
getline(cin, b);
int N = a.size();
int M = b.size();
int cod1 = 0;
int cod2 = 0;
int cod3 = 0;
for(int i = 0; i < N; ++ i)
{
cod1 = (cod1 * B1 + a[i] - 'A') % mod;
cod2 = (cod2 * B2 + a[i] - 'A') % mod;
cod3 = (cod3 * B3 + a[i] - 'A') % mod;
}
int pw1 = 1;
int pw2 = 1;
int pw3 = 1;
for(int i = 1; i < N; ++ i)
{
pw1 = (pw1 * B1) % mod;
pw2 = (pw2 * B2) % mod;
pw3 = (pw3 * B3) % mod;
}
int pre1 = 0;
int pre2 = 0;
int pre3 = 0;
for(int i = 0; i < N; ++ i)
{
pre1 = (pre1 * B1 + b[i] - 'A') % mod;
pre2 = (pre2 * B2 + b[i] - 'A') % mod;
pre3 = (pre3 * B3 + b[i] - 'A') % mod;
}
if(cod1 == pre1 && cod2 == pre2 && cod3 == pre3) sol.push_back(1);
for(int i = N; i < M; ++ i)
{
pre1 = (pre1 - ((b[i - N] - 'A') * pw1) % mod + mod) % mod;
pre2 = (pre2 - ((b[i - N] - 'A') * pw2) % mod + mod) % mod;
pre3 = (pre3 - ((b[i - N] - 'A') * pw3) % mod + mod) % mod;
pre1 *= B1;
pre2 *= B2;
pre3 *= B3;
pre1 += b[i] - 'A';
pre2 += b[i] - 'A';
pre3 += b[i] - 'A';
pre1 %= mod;
pre2 %= mod;
pre3 %= mod;
if(cod1 == pre1 && cod2 == pre2 && cod3 == pre3) sol.push_back(i - N + 1);
}
cout << sol.size() << '\n';
for(int i = 0; i < 1000 && i < sol.size(); ++ i)
cout << sol[i] << ' ';
cout << '\n';
cin.close();
cout.close();
return 0;
}