POJ 1200 Crazy Search(RK)

8055 ワード

に言及
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; }