Pagini recente » Cod sursa (job #75380) | Cod sursa (job #2302977) | Cod sursa (job #1802288) | Cod sursa (job #3233369) | Cod sursa (job #2096777)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int base = 103;
const int nmax = 2000000;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string s1;
string s2;
ull h[nmax]; //hash-urile prefixelor (se folosesc la rolling hash)
ull target; //hash-ul string-ului ce trebuie gasit
ull shift;
vector <int> sol;
int nsol;
int main()
{
in >> s1;
in >> s2;
target = 0;
shift = 1;
for(int i=0; i < s1.size(); i++) {
target = target * base + (s1[i] - 'A');
shift = shift * base;
}
h[0] = s2[0] - 'A';
for(int i = 1; i < s2.size(); i ++)
h[i] = h[i-1] * base + (s2[i] - 'A');
for(int i = 0; i + s1.size() <= s2.size(); i ++)
{
ull pretender = h[i+s1.size()-1];
if(0 < i)
pretender -= (h[i-1]*shift);
if(pretender == target){
nsol ++;
if(nsol <= 1000)
sol.push_back(i);
}
}
out << nsol << "\n";
for(int i = 0;i < sol.size();i ++)
out << sol[i] << " ";
return 0;
}