Pagini recente » Cod sursa (job #2449599) | Cod sursa (job #373327) | Cod sursa (job #453860) | Cod sursa (job #221868) | Cod sursa (job #3229034)
#include <bits/stdc++.h>
using namespace std;
#define d 256
const int q = 1e6 + 7;
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
std::string s1 , s2;
vector<int>ans;
int h , p , t;
int main()
{
p = 0;
t = 0;
h = 1;
fin >> s1 >> s2;
for(int i = 0 ; i < s1.size() - 1 ; ++i)
h = (h * d) % q;
for(int i = 0 ; i < s1.size() ; ++i)
{
p = (d * p + s1[i]) % q;
t = (d * t + s2[i]) % q;
}
for(int i = 0 ; i <= s2.size() - s1.size() ; ++i)
{
// fout << p << " " << t << "\n";
if(p == t){
bool ok = true;
for(int j = 0 ; j < s1.size() && ok; ++j)
{
if(s1[j] != s2[i + j])ok = false;
}
if(ok == true)ans.push_back(i);
}
t = (d * (t - s2[i] * h) + s2[i + s1.size()]) % q;
// t = (d * (t - s2[i] * h) + s2[i + s1.size()]) % q;
if(t < 0)t += q;
}
//fout << h << "\n";
fout << ans.size() << "\n";
for(int i = 0 ; i < std::min(1000 , (int)ans.size()) ; ++i)
{
fout << ans[i] << " ";
}
}