Pagini recente » Cod sursa (job #2751170) | Cod sursa (job #9719) | Poze preONI 2007 - premiere | Cod sursa (job #1186258) | Cod sursa (job #3170599)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
string a, b;
const long long bz=41, MOD1=20000147, MOD2=1000000007;
int n, m;
vector <int> sol;
struct stuts
{
long long v1=0, v2=0, p1=1, p2=1;
void next_stuts(char a, char b)
{
v1=(v1-(1LL*a*p1)%MOD1+MOD1)%MOD1;
v1=(v1*bz)%MOD1;
v1=(v1+1LL*b)%MOD1;
v2=(v2-(1LL*a*p2)%MOD2+MOD2)%MOD2;
v2=(v2*bz)%MOD2;
v2=(v2+1LL*b)%MOD2;
// cout << v1 << " " << v2 << endl;
}
stuts(int k, string y)
{
for (int i=k-1;i>=0;--i)
{
//cout << p1 << endl;
v1=(v1+(p1*y[i])%MOD1)%MOD1;
v2=(v2+(p2*y[i])%MOD2)%MOD2;
if (i>0){
p1=(p1*bz)%MOD1;
p2=(p2*bz)%MOD2;}
}
// cout << v1 << " " << v2 << endl;
}
bool operator == (const stuts other)const{
return (v1==other.v1)&&(v2==other.v2);
}
};
void solve()
{
fin>>b>>a;
int m=b.size(),n=a.size();
stuts pat(m,b), sir(m,a);
int c=0;
for (int i=m-1;i<n;++i)
{
if (pat==sir){
c++;
sol.push_back(i-m+1);
}
sir.next_stuts(a[i-m+1],a[i+1]);
}
fout << c << "\n";
int nr=sol.size();
for (int i=0;i<min(n,nr);++i)
fout << sol[i] << " ";
}
int main()
{
solve();
return 0;
}