程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva 1358 - Generator(KMP+期望)

uva 1358 - Generator(KMP+期望)

編輯:C++入門知識

uva 1358 - Generator(KMP+期望)


題目鏈接:uva 1358 - Generator

題目大意:給定n,表示有n中字符,然後給定一個字符串S,一開始字符串為空,現在每次隨機生成一個1~n的字符添加到字符串末尾,問說字符串包含S為子串的生成次數期望。

解題思路:首先要對S進行預處理,求出失配數組。

定義dp[i]表示末尾部分匹配了i個S串所需要的次數期望,每次枚舉可能出現的字符1~n。對於S字符串,i+1肯定是確定的字符,所以對於其他字符肯定是不匹配的。
假設現在生成了k字符,並且說k字符不等於S[i+1],那麼根據S的失配數組,我們可以確定目前還匹配幾個字符,(類似KMP匹配問題),假設有匹配j個字符,那麼也就是說從匹配j個到匹配i個我們還要重新生成dp[i] - dp[j]次(期望)。
於是f(i)(從匹配i-1到匹配i個需要生成次數的期望)即有公式f(i)=1+∑i=1n(dp[i?1]?dp[lose(k)])+n?1nf(i)(lose(k)為對應生成字符為k的情況下還匹配的字符數)
dp[i] = dp[i-1] + f(i)

#include 
#include 
#include 

using namespace std;
typedef long long ll;

const int maxn = 20;

int len, jump[maxn];

void get_jump(char* s) {
    int p = 0;
    len = strlen(s+1);
    for (int i = 2; i <= len; i++) {
        while (p && s[p+1] != s[i])
            p = jump[p];

        if (s[p+1] == s[i])
            p++;
        jump[i] = p;
    }
}

ll solve () {
    int n;
    ll dp[maxn];
    char s[maxn];

    scanf("%d%s", &n, s+1);

    get_jump(s);
    dp[0] = 0;

    for (int i = 1; i <= len; i++) {

        ll& ans = dp[i];
        ans = dp[i-1] + n;

        for (int j = 0; j < n; j++) {
            if (s[i] == 'A' + j)
                continue;

            int p = i-1;
            while (p && s[p+1] != j + 'A')
                p = jump[p];

            if (s[p+1] == j + 'A')
                p++;

            ans += dp[i-1] - dp[p];
        }
    }

    return dp[len];
}

int main () {
    int cas;
    scanf("%d", &cas);
    for (int kcas = 1; kcas <= cas; kcas++) {
        printf("Case %d:\n%lld\n", kcas, solve());

        if (kcas < cas)
            printf("\n");
    }
    return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved