Nu aveti permisiuni pentru a descarca fisierul grader_test8.in
Cod sursa(job #1963679)
Utilizator | Data | 12 aprilie 2017 18:15:45 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 80 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.49 kb |
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define in "strmatch.in"
#define out "strmatch.out"
#define NMAX (2000000 + 7)
#define MOD (1000000000 + 7)
#define pb push_back
#define phi 52
using namespace std;
int szeA, szeB, pw[NMAX], hashValue, Hash, sze;
char A[NMAX], B[NMAX];
vector <int> sol;
int val(char ch) // OK
{
if(ch == 0) return 0;
if(ch <= 'z' && ch >= 'a') return (ch-'a');
return (26 + ch - 'A');
}
int main()
{
freopen(in, "r", stdin);
freopen(out, "w", stdout);
scanf("%s\n%s\n", A+1, B+1);
szeA = strlen(A+1);
szeB = strlen(B+1);
pw[0] = 1;
for(int i = 1; i<= szeA; ++i) pw[i] = (1LL * pw[i-1] * phi)%MOD;
for(int i = 1; i<= szeA; ++i) hashValue = (1LL*hashValue*phi + val(A[i]))%MOD;
for(int i = 1; i<= szeB; ++i)
{
if(i >= szeA)
{
Hash = (Hash - (1LL * val(B[i-szeA]) * pw[szeA-1]) % MOD + MOD)%MOD;
}
Hash = (1LL * Hash * phi + val(B[i]))%MOD;
if(i >= szeA)
{
if(Hash == hashValue)
{
bool f = 1;
for(int j = 1; j<= szeA; ++j)
{
if(A[j] != B[i-szeA + j]) {f = 0; break;}
}
if(f == 1) sol.pb(i-szeA);
}
}
}
sze = sol.size();
printf("%d\n", sze);
for(int i = 0; i< min(1000, sze); ++i) printf("%d ", sol[i]);
printf("\n");
return 0;
}