Pagini recente » Monitorul de evaluare | Cod sursa (job #1514051) | Cod sursa (job #958041) | Cod sursa (job #381517) | Cod sursa (job #2010316)
#include <cstdio>
#include <cstring>
/*
#define M 62
#define MOD1 1000003
#define MOD2 1000033
*/
#define M 73
#define MOD1 100007
#define MOD2 100021
using namespace std;
typedef int lint;
FILE *f, *g;
int rz[1009];
int rez;
char a[2000009];
char b[2000009];
void readFile()
{
f = fopen("strmatch.in", "r");
fscanf(f, "%s", a);
fscanf(f, "%s", b);
fclose(f);
}
int nr(char c)
{
return c;
if(c >='0' && c <= '9')
return c - '0' + 1;
if(c >= 'a' && c <= 'z')
return 10 + c - 'a' + 1;
if(c >= 'A' && c <= 'Z')
return 10 + 26 + c - 'A' + 1;
return 0;
}
void solve()
{
int n = strlen(a);
int m = strlen(b);
if(n > m)
{
rez = 0;
return;
}
lint p1 = 1;
lint p2 = 1;
lint r1 = 0;
lint r2 = 0;
int i;
for(i = 0; i < n; i ++)
{
r1 = r1 * M + nr(a[i]);
r1 %= MOD1;
r2 = r2 * M + nr(a[i]);
r2 %= MOD2;
if(i > 0)
{
p1 *= M;
p1 %= MOD1;
p2 *= M;
p2 %= MOD2;
}
}
lint h1 = 0;
lint h2 = 0;
for(i = 0; i < n; i ++)
{
h1 = h1 * M + nr(b[i]);
h1 %= MOD1;
h2 = h2 * M + nr(b[i]);
h2 %= MOD2;
}
if(h1 == r1 && h2 == r2)
rz[++ rez] = 0;
for(i = n; i < m; i ++)
{
// printf("%lld %lld\n", h1, h2);
h1 = h1 - p1 * nr(b[i - n]) % MOD1 + MOD1;
h1 %= MOD1;
h1 = h1 * M + nr(b[i]);
h1 %= MOD1;
h2 = h2 - p2 * nr(b[i - n]) % MOD2 + MOD2;
h2 %= MOD2;
h2 = h2 * M + nr(b[i]);
h2 %= MOD2;
// printf("%lld %lld\n", h1, h2);
/*if(i == 3)
{
printf("%lld %lld\n", h1, h2);
printf("%lld %lld\n", r1, r2);
}*/
if(h1 == r1 && h2 == r2)
{
rez ++;
if(rez <= 1000)
rz[rez] = i - n + 1;
}
}
}
void printFile()
{
g = fopen("strmatch.out", "w");
fprintf(g, "%d\n", rez);
int i;
for(i = 1; i <= rez && i <= 1000; i ++)
fprintf(g, "%d ", rz[i]);
fprintf(g, "\n");
fclose(g);
}
int main()
{
readFile();
solve();
printFile();
return 0;
}