Pagini recente » Cod sursa (job #1673612) | Cod sursa (job #44604) | Cod sursa (job #1932220) | Cod sursa (job #793978) | Cod sursa (job #629526)
Cod sursa(job #629526)
#include<fstream>
#include<cstring>
#define NMAX 2000010
#define B 83
#define MOD 666013
using namespace std;
string c1, c2;
int n, m, st[NMAX], P=1, ha, hb, fin=0;
short a[NMAX], b[NMAX];
ifstream f("strmatch.in");
ofstream g("strmatch.out");
inline int cif(char c)
{
if (c>='A' && c<='Z') return c-'A';
else if (c>='a' && c<='z') return'Z'-'A'+c-'a'+1;
return 'Z'-'A'+'z'-'a'+2+c-'0';
}
void Preprop()
{
int i;
n=c1.size(); m=c2.size();
for (i=0; i<m; ++i) a[i+1]=cif(c2[i]);
for (i=0; i<n; ++i)
{
b[i+1]=cif(c1[i]);
hb=((hb*B)%MOD+b[i+1])%MOD;
if (i>0)P=(P*B)%MOD;
}
for (i=0; i<n; ++i)
ha=((ha*B)%MOD+a[i+1])%MOD;
}
void Solve()
{
int i;
if (ha==hb && !c2.compare(0, n, c1)) st[++fin]=0;
for (i=2; i<=m-n+1; ++i)
{
//ha=(((((ha-(a[i-1]*P)%MOD)+MOD)%MOD)*B)%MOD + a[n+i-1])%MOD;
/*pas1*/ ha=ha-((P*a[i-1])%MOD);
if (ha<0) ha+=MOD;
/*pas2*/ ha=(ha*B)%MOD;
/*pas3*/ ha=(ha+a[i+n-1])%MOD;
if (ha==hb && !c2.compare(i-1, n, c1))
{
++fin;
if (fin<1001) st[fin]=i-1;
}
}
}
void Write()
{
int i, mm=min(1000, fin);
g<<fin<<"\n";
for (i=1; i<=mm; ++i) g<<st[i]<<" ";
}
int main()
{
getline(f, c1);
getline(f, c2);
Preprop();
Solve();
Write();
f.close();
g.close();
return 0;
}