投資錢景>買台積電就對了老王現身說法關鍵字魅力!攝影界美人正妹指定相機款籌400萬醫藥費 俞嫻...
2013-05-12 20:08:00 人氣(251) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][最小表示法、窮舉] 12494 - Distinct Substring

0
收藏
0
推薦

BGC TRUST IUPC 2012

 

Problem A

Distinct Substring

 

 

Given a string S, Dexter wants to find the number of different substrings in S. He considers two substrings same if they have a cyclic permutation which is same.

 

If is a string of length n then it has n cyclic permutations and they are  for all . (Note that,  are non-existing).

 

For example, if T = “abcd” there are 4 cyclic permutations and they are: “abcd”, “bcda”, “cdab” and “dabc”.

 

So, string “aba”, “aab” and “baa” are all considered same. But “abc” and “bac” are different as there is no cyclic permutation of them which are same.

 

 

Input

 

First line contains an integer T (T <= 50) denoting the number of test cases. Each of the next T lines contains a string S which is composed of only lowercase latin letters. You can assume that the length of S is between 1 and 200 inclusive.

 

 

Output

 

For each test case, output the number of different substrings in a line.

 

 

Sample Input

Output for Sample Input

3

abcba

aab

zzxzz

10

5

7

 

 

Explanation: If S = “abcba” there are 10 cyclic different substrings and they are: “a”, “b”, “c”, “ab”, “bc”, “abc”, “bcb”, “cba”, “abcb” and “abcba”.

 

 

Problemsetter: Tasnim Imran Sunny

Special Thanks: Kazi Rakibul Hasan


將所有可能列舉出來 O(|S|^2),再找到其最小表示法 O(|S|),
然後使用雜湊或者是 set 去解決。
最後是 O(|S|^2)

#include <stdio.h>
#include <string.h>
#include <set>
#include <iostream>
using namespace std;
int MinExp(const char *s, const int slen) {
    int i = 0, j = 1, k = 0, x, y, tmp;
    while(i < slen && j < slen && k < slen) {
        x = i + k;
        y = j + k;
        if(x >= slen)    x -= slen;
        if(y >= slen)    y -= slen;
        if(s[x] == s[y]) {
            k++;
        } else if(s[x] > s[y]) {
            i = j+1 > i+k+1 ? j+1 : i+k+1;
            k = 0;
            tmp = i, i = j, j = tmp;
        } else {
            j = i+1 > j+k+1 ? i+1 : j+k+1;
            k = 0;
        }
    }
    return i;
}
int main() {
    int t;
    char s[1005], ss[1005];
    scanf("%d", &t);
    while(t--) {
        scanf("%s", s);
        int len = strlen(s);
        int i, j, k;
        set<string> S[205];
        for(i = 0; i < len; i++) {
            for(j = 0; i+j < len; j++) {
                //s[i...i+j]
                int pos = MinExp(s+i, j+1)+i;
                //puts("");
                for(k = 0; k <= j; k++) {
                    ss[k] = s[pos];
                    pos++;
                    if(pos == i+j+1)    pos = i;
                }
                ss[k] = '\0';
                S[k].insert(ss);
            }
        }
        int ret = 0;
        for(i = 0; i <= len; i++)
            ret += S[i].size();
        printf("%d\n", ret);
    }
    return 0;
}

12494Distinct Substring最小表示法窮舉
台長:Morris
人氣(251) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][模擬] 1544 - Simple Arithmetics
此分類上一篇:[UVA][循環節] 12620 - Fibonacci Sum

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文