Pagini recente » Monitorul de evaluare | Cod sursa (job #1629971) | Monitorul de evaluare | Cod sursa (job #2024992) | Cod sursa (job #629414)
Cod sursa(job #629414)
#include<fstream>
#include<cstring>
#define NMAX 2000010
#define B 53
#define MOD 104729
using namespace std;
char c1[NMAX], c2[NMAX];
int n, m, st[NMAX], dr[NMAX], P=1, ha, hb, fin=0;
short a[NMAX], b[NMAX];
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int cif(char c)
{
if (c>='A' && c<='Z') return c-'A';
else return 'Z'-'A'+c-'a'+1;
}
void Preprop()
{
int i;
n=strlen(c1); m=strlen(c2);
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;
}
int match(int st, int dr)
{
int ok=1, i;
for (i=1; i<=n; ++i)
if (b[i]!=a[i+st-1]) {ok=0; break;}
return ok;
}
void Solve()
{
int i;
if (ha==hb && match(1, n)) st[++fin]=1, dr[fin]=n;
for (i=2; i<=m-n+1; ++i)
{
ha=(((((ha-(a[i-1]*P)%MOD)+MOD)%MOD)*B)%MOD + a[n+i-1])%MOD;
if (ha==hb && match(i, n-i+1)) st[++fin]=i, dr[fin]=n-i+1;
}
}
void Write()
{
int i;
g<<fin<<"\n";
for (i=1; i<=min(1000, fin); ++i) g<<st[i]-1<<" ";
}
int main()
{
f.getline(c1, NMAX);
f.getline(c2, NMAX);
Preprop();
Solve();
Write();
f.close();
g.close();
return 0;
}