程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> uva 1401 Remember the Word ( Trie + DP )

uva 1401 Remember the Word ( Trie + DP )

編輯:關於C++

題意:給出n(n<=4000)個單詞和一個字符串(len<=300000),求把這個字符串分解成若干個單詞的拼接,有多少種方法

思路:Trie,先把單詞建成Trie,然後進行dp,dp[i]表示以字符串中第i個字母為開頭的情況,然後每個狀態只要在Trie樹上找到相應的字母開頭的單詞,然後dp[i] = sum{dp[i + len(x)]}進行狀態轉移即可 這個x是n個單詞中的一個,可以用Trie查詢

 

code:

 

#include
#include
#include
using namespace std;

const int maxn = 300005;
const int MOD = 20071027;

int ch[maxn][26];
int val[maxn];
int sz;
int idx(char c){return c-'a';}
void insert(char* s){
    int u = 0;
    int len = strlen(s);
    for(int i = 0; i < len; i++){
        int c = idx(s[i]);
        if(!ch[u][c]){
            memset(ch[sz], 0, sizeof(ch[sz]));
            val[sz] = 0;
            ch[u][c] = sz++;
        }
        u = ch[u][c];
    }
    val[u] = 1;
}

void init(){
    sz = 1;
    memset(ch[0],0,sizeof(ch[0]));
    int m;
    scanf("%d",&m);
    char str[105];
    while(m--){
        scanf("%s",str);
        insert(str);
    }
}
int d[maxn];
void find(int id, char* s){
    d[id] = 0;
    int u = 0;
//    int len = strlen(s);
    for(int i = id; s[i]; i++){
        int c = idx(s[i]);
        if(!ch[u][c]) return;
        u = ch[u][c];
        if(val[u]) d[id] = (d[id]+d[i+1])%MOD;
    }
}
void solve(char* s){
    int len = strlen(s);
    d[len] = 1;
    for(int i = len-1; i >= 0; i--){
        find(i, s);
    }
    printf("%d\n",d[0]);
}
int main(){
    int cas = 0;
    char s[maxn];
    while(scanf("%s",s) != EOF){
        init();
        printf("Case %d: ",++cas);
        solve(s);
    }
    return 0;
}

注意:

 

find 函數中千萬不能strlen();不然超時T_T。。因為每次調用都會求一次長度,時間復雜度是0(N*N);

 

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