Pagini recente » Cod sursa (job #108972) | Cod sursa (job #1279925) | Cod sursa (job #3271010) | Cod sursa (job #2685436) | Cod sursa (job #1386959)
#include<fstream>
#include<algorithm>
#define mod1 1000021
#define mod2 100007
#define p 73
using namespace std;
string s1,s2;
int sol[1001];
int i,j,k,m,n,u;
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
getline(cin,s1);
getline(cin,s2);
//cout<<s2;
n=s1.size()-1;
m=s2.size()-1;
int hash1,hash2,p1,hash3,hash4,p2;
hash3=hash4=hash1=hash2=0;
p1=1;
p2=1;
for (i=0; i<n; ++i)
{
hash1=(hash1*p+s1[i])%mod1;
hash2=(hash2*p+s1[i])%mod2;
hash3=(hash3*p+s2[i])%mod1;
hash4=(hash4*p+s2[i])%mod2;
if (i>0)
{
p1=(p1*p)% mod1;
p2=(p2*p)% mod2;
}
}
if (hash1==hash3 && hash2==hash4) sol[++u]=0;
for (i=n; i<m; ++i)
{
hash3=((hash3-((s2[i-n]*p1)%mod1)+mod1)*p+s2[i])%mod1;
hash4=((hash4-((s2[i-n]*p2)%mod2)+mod2)*p+s2[i])%mod2;
if (hash1==hash3 && hash2==hash4) sol[++u]=i-n+1;
}
cout<<u<<"\n";
for (i=1; i<=min(u,1000); ++i) cout<<sol[i]<<" ";
return 0;
}