首爾性愛美術館18禁的藝術來自星星的你也會打廣告?法人:14檔今年本業虧定了不捨學生找「槌」 高中...
2012-03-29 21:50:49 人氣(306) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[ZJ][最小表示法][環同構判定][a442] Necklace Problem (NP)

0
收藏
0
推薦

內容 :

「題目總是唬人的,事實上並沒有那麼難」

給你兩個項鍊,這兩條項鍊上都有 n 顆珠子(用 0 ~ 9 表示之),請判定這兩條項鍊是否相同。

記住項鍊可翻面。

 

 

後文:自從上了大學,就不來 ZJ 了 ... 因此題目如有雷同,請通知下架。

輸入說明 :

有多筆測資,每組有兩個長度相同的字串來代表兩個項鍊。

0 < n < 10000

 

輸出說明 :

相同請輸出 same, 不同請輸出 difference

範例輸入 :

4263
6234
4263
4362

範例輸出 :

difference
same

提示 :

頭跟尾要接起來,因為是項鍊。 用 gets 會有問題, scanf 則沒有問題 ...

出處 :

Morris (管理:morris1028)





#include <stdio.h>
#include <string.h>
int MinExpSame(const char *A, const char *B, const int slen) {
    int i = 0, j = 0, k = 0;
    int 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(A[x] == B[y]) {
            k++;
            if(k == slen) {
                return 1;
            }
        } else if(A[x] < B[y]) {
            i = i+k+1;
            k = 0;
        } else {
            j = j+k+1;
            k = 0;
        }
    }
    return 0;
}
int main() {
    char A[10001], B[10001], tmp;
    int i, j;
    while(scanf("%s %s", A, B) == 2) {
        if(MinExpSame(A, B, strlen(A)) == 0) {
            for(i = 0, j = strlen(A)-1; i < j; i++, j--)
                tmp = B[i], B[i] = B[j], B[j] = tmp;
            if(MinExpSame(A, B, strlen(A)) == 0)
                puts("difference");
            else
                puts("same");
        } else
            puts("same");
    }
    return 0;
}

最小表示法環同構判定a442Necklace Problem (NP)
台長:Morris
人氣(306) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 其他題目 |
此分類下一篇:[機率][問題] 檢驗策略?
此分類上一篇:[中興資工][程設][作業HW12]

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

(有*為必填)
詳全文