Pagini recente » Cod sursa (job #330982) | Cod sursa (job #2638673) | Cod sursa (job #863153) | Cod sursa (job #206262) | Cod sursa (job #2853795)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int N = 4e6, d = 62, q = 666013;
string a, b, s;
long long a_len, b_len, s_len;
long long k, cnt;
vector <int> ans;
int main()
{
fin>>a>>b;
s='$'+a+'$'+b;
a_len=a.size();
b_len=b.size();
s_len=s.size();
if(a_len>b_len)
{
fout<<0;
return 0;
}
int hash_a=0, hash_b=0;
int h=1;
for(int i=0; i<a_len-1; i++)
h=(h*d)%q;
for(int i=0; i<a_len; i++)
{
hash_a = (d * hash_a + a[i]) % q;
hash_b = (d * hash_b + b[i]) % q;
}
int i, j;
for(i=0; i<b_len-a_len; i++)
{
if(hash_a==hash_b)
{
bool ok=1;
for(j=0; j<a_len; j++)
{
if(a[j] != b[i+j])
{
ok=0;
break;
}
if(ok)
continue;
}
if(j==a_len)
ans.push_back(i);
}
if(i<b_len-a_len)
{
hash_b=(d*(hash_b-b[i]*h)+ b[i+a_len])%q;
if(hash_b<0)
hash_b+=q;
}
}
fout<<ans.size()<<'\n';
for(int i=0; i<ans.size(); i++)
fout<<ans[i]<<" ";
return 0;
}