Morris' Blog

2012-03-29 21:50:49Morris

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

留言 0 收藏 0 推薦 0

內容：

「題目總是唬人的，事實上並沒有那麼難」
給你兩個項鍊，這兩條項鍊上都有 n 顆珠子(用 0 ~ 9 表示之)，請判定這兩條項鍊是否相同。
記住項鍊可翻面。 
 
 
後文：自從上了大學，就不來 ZJ 了 ... 因此題目如有雷同，請通知下架。

輸入說明：

有多筆測資，每組有兩個長度相同的字串來代表兩個項鍊。
0 < n < 10000
 

輸出說明：

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

範例輸入：

範例輸出：

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;
}