Pagini recente » Istoria paginii runda/vali_tigan/clasament | Cod sursa (job #2048394) | Cod sursa (job #2569691) | Cod sursa (job #3199821) | Cod sursa (job #3170573)
#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
{
int v1=0, v2=0, p=1;
void next_stuts(char a, char b)
{
v1=(v1-a*p)%MOD1;
v1=(v1*bz)%MOD1;
v1+=b;
v2=(v2-a*p)%MOD2;
v2=(v2*bz)%MOD2;
v2+=b;
// cout << v1 << " " << v2 << endl;
}
stuts(int k, string y)
{
for (int i=k-1;i>=0;--i)
{
v1+=(p*y[i])%MOD1;
v2+=(p*y[i])%MOD2;
p*=bz;
}
p/=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;
}