Pagini recente » Cod sursa (job #1716464) | Cod sursa (job #2789096) | Cod sursa (job #102789) | Cod sursa (job #383847) | Cod sursa (job #629614)
Cod sursa(job #629614)
# include <fstream>
# include<string>
using namespace std;
int hash11, hash12, hash21, hash22,na,nb,p1,p2,i,nr,sol[2000001];
string a,b;
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>a;
f>>b;
p1=p2=1;
hash11=hash12=hash21=hash22=0;
na=a.length();
nb=b.length();
for (i=0; i<na; i++)
{
hash11=(hash11*73+a[i]) % 100021;
hash12=(hash12*73+a[i]) % 100007;
if (i!=0)
{
p1=(p1*73)%100021;
p2=(p2*73)%100007;
}
}
if (na>nb) { printf("0\n"); return 0;}
for (i=0; i<na; i++)
{
hash21=(hash21*73+b[i])% 100021;
hash22=(hash22*73+b[i])% 100007;
}
nr=0;
if (hash11==hash21 && hash12==hash22)
{sol[0]=1; nr++;}
for (i=na; i<nb; i++)
{
hash21=((hash21-(b[i-na]*p1)% 100021+100021)*73+b[i])%100021;
hash22=((hash22-(b[i-na]*p2)% 100007+100007)*73+b[i])%100007;
if (hash11==hash21 && hash12==hash22) {sol[i-na+1]=1; nr++;}
}
g<<nr<<"\n";
if (nr>=1000)
{
nr=0;
for (i=0; i<nb && nr<1000; i++)
if (sol[i])
{
nr++;
g<<i<<" ";
}
}
//else
//{
// nr=0;
// for (i=0; i<nb && nr<=1000; i++)
// if (sol[i])
//// {
//// nr++;
// g<<i<<" ";
// }
//}
g<<"\n";
return 0;
}