Pagini recente » Cod sursa (job #2492117) | Cod sursa (job #2424430) | Cod sursa (job #1186736) | Autentificare | Cod sursa (job #3170582)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
string a, b;
const int bz=41, MOD1=1000000007, MOD2=20000147;
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-(a*p1)%MOD1)%MOD1;
v1=(v1*bz)%MOD1;
v1=(v1+b)%MOD1;
v2=(v2-(a*p2)%MOD2)%MOD2;
v2=(v2*bz)%MOD2;
v2=(v2+b)%MOD2;
// cout << v1 << " " << v2 << endl;
}
stuts(int k, string y)
{
for (int i=k-1;i>=0;--i)
{
v1+=(p1*y[i])%MOD1;
v2+=(p2*y[i])%MOD2;
p1=(p1*bz)%MOD1;
p2=(p2*bz)%MOD2;
}
p1/=bz;
p2/=bz;
// 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;
}