Pagini recente » Cod sursa (job #1250344) | Cod sursa (job #815076) | Cod sursa (job #1395587) | Cod sursa (job #652445) | Cod sursa (job #2011632)
#include <fstream>
#include <vector>
using namespace std;
const int P = 73;
const int MOD1 = 100007;
const int MOD2 = 100021;
vector <int> sol;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int main()
{
string a;
string b;
cin >> a >> b;
int P1 = 1, P2 = 1;
int s1 = 0, s2 = 0;
for(int i = 0;i < a.size(); ++i){
s1 = (s1 * P + a[i]) % MOD1;
s2 = (s2 * P + a[i]) % MOD2;
if(i != 0){
P1 = P1 * P % MOD1;
P2 = P2 * P % MOD2;
}
}
int hash1 = 0, hash2 = 0;
for(int i = 0; i < a.size(); ++i){
hash1 = (hash1 * P + b[i]) % MOD1;
hash2 = (hash2 * P + b[i]) % MOD2;
}
int nr = 0;
if(hash1 == s1 && hash2 == s2){
sol.push_back(1);
++nr;
}
for(int i = a.size(); i < b.size(); ++i){
hash1 = (((hash1 - b[i-a.size()] * P1) % MOD1 + MOD1) * P + b[i]) % MOD1;
hash2 = (((hash2 - b[i-a.size()] * P2) % MOD2 + MOD2) * P + b[i]) % MOD2;
if(hash1 == s1 && hash2 == s2){
sol.push_back(i-a.size() + 1);
++nr;
}
}
cout << nr << '\n';
for(int i = 0; i < min(1000, nr); ++i){
cout << sol[i] << ' ';
}
return 0;
}