Pagini recente » Cod sursa (job #1382249) | Cod sursa (job #1514337) | Cod sursa (job #2134729) | Cod sursa (job #2221898) | Cod sursa (job #629514)
Cod sursa(job #629514)
#include<fstream>
#include<cstring>
#define NMAX 2000010
#define B 83
#define MOD 666013
using namespace std;
string c1, c2;
int n, m, st[1010], 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 (fin!=1000 && ha==hb && !c2.compare(0, n, c1)) st[++fin]=0;
for (i=2; i<=m-n+1; ++i)
{
/*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 (fin!=1000 && ha==hb && !c2.compare(i-1, n, c1)) 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;
}