POJ 1200 Crazy Search(RK)
8055 ワード
に言及
NC文字からなる文字列を与えて、長さNの異なるサブ列の個数を求めます
考え方:
NC文字しかないので、アルファベット番号、0~NC-1を数字に変換すれば、文字列をNC進数の数字に表すことができ、すべての文字列が表す数字が一意で、10進数に変換する数も一意です!
10のバイナリ表現が1010しかないように
たとえば
NC文字からなる文字列を与えて、長さNの異なるサブ列の個数を求めます
考え方:
NC文字しかないので、アルファベット番号、0~NC-1を数字に変換すれば、文字列をNC進数の数字に表すことができ、すべての文字列が表す数字が一意で、10進数に変換する数も一意です!
10のバイナリ表現が1010しかないように
たとえば
3 4
daababac
d = 3
a = 0
b = 1
c = 2
daa = 3 * 4 ^ 2 + 0 * 4 ^ 1 + 0 * 4 ^ 0 = 48
//vs1.0
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 16000000
char str[MAX];
bool hash[MAX];
int ancii[128];
int main() {
int N, NC;
while (scanf("%d%d%s", &N, &NC, str) != EOF) {
memset(hash, true, sizeof(hash));
memset(ancii, 0, sizeof(ancii));
int cnt = 0;
for (char *s=str; *s; ++s) {
if (!ancii[*s]) {
ancii[*s] = ++cnt;
if (NC == cnt) break;
}
}
int sum;
int ans = 0;
int len = strlen(str) - N + 1;
for (int i=0; i<len; ++i) {
sum = 0;
for (int j=0; j<N; ++j) sum = sum * NC + (ancii[str[i+j]] - 1);
if (hash[sum]) {
++ans;
hash[sum] = false;
}
}
printf ("%d
", ans);
}
return 0;
}
//vs2.0
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 16000000
char str[MAX];
bool hash[MAX];
int ancii[128];
int main() {
int N, NC;
while (scanf("%d%d%s", &N, &NC, str) != EOF) {
memset(hash, true, sizeof(hash));
memset(ancii, 0, sizeof(ancii));
int cnt = 0;
for (char *s=str; *s; ++s) {
if (!ancii[*s]) {
ancii[*s] = ++cnt;
if (NC == cnt) break;
}
}
int sum = 0;
int tmp = 1;
for (int i=0; i<N; ++i) {
tmp *= NC;
sum = sum * NC + ancii[str[i]] - 1;
}
tmp /= NC;
hash[sum] = false;
int ans = 1;
int len = strlen(str);
for (int i=N; i<len; ++i) {
sum = (sum - tmp * (ancii[str[i-N]]-1)) * NC + ancii[str[i]] - 1;
if (hash[sum]) {
++ans;
hash[sum] = false;
}
}
printf ("%d
", ans);
}
return 0;
}