C語言判斷字符串是否為旋轉字符串：雙向旋轉檢測法

C語言判斷字符串是否為旋轉字符串：雙向旋轉檢測法

判斷字符串 s2 是否為 s1 的旋轉變體。如 "AABCD" 與 "ABCDA"。思路：嘗試所有可能的左旋/右旋位數，對比是否相等。

算法邏輯

1. 對 s1 嘗試 k=1..len-1 位左旋
2. 每次左旋後與 s2 比較
3. 若相等返回真
4. 同理嘗試右旋
5. 全部失敗返回假

完整代碼（修正原文變量錯誤）

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>

void reverse(char *l, char *r) {
    while (l < r) {
        char t = *l; *l = *r; *r = t;
        l++; r--;
    }
}

void left_rotate(char *s, int k) {
    int len = strlen(s);
    k %= len;
    reverse(s, s + k - 1);
    reverse(s + k, s + len - 1);
    reverse(s, s + len - 1);
}

void right_rotate(char *s, int k) {
    int len = strlen(s);
    k %= len;
    reverse(s, s + len - k - 1);
    reverse(s + len - k, s + len - 1);
    reverse(s, s + len - 1);
}

int is_rotation(const char *s1, const char *s2) {
    if (strlen(s1) != strlen(s2)) return 0;
    if (strcmp(s1, s2) == 0) return 1;
    
    char buf[100];
    strcpy(buf, s1);
    int len = strlen(buf);
    
    for (int k = 1; k < len; k++) {
        left_rotate(buf, k);
        if (strcmp(buf, s2) == 0) return 1;
        // 恢復原串嘗試右旋
        strcpy(buf, s1);
        right_rotate(buf, k);
        if (strcmp(buf, s2) == 0) return 1;
        strcpy(buf, s1);  // 重置
    }
    return 0;
}

int main() {
    char s1[] = "AABCD";
    char s2[] = "ABCDA";
    printf("%s\n", is_rotation(s1, s2) ? "是旋轉字符串" : "非旋轉字符串");
    system("pause");
    return 0;
}

更優解法：字符串拼接法 O(n)

int is_rotation_fast(const char *s1, const char *s2) {
    if (strlen(s1) != strlen(s2)) return 0;
    char *double_s1 = malloc(2 * strlen(s1) + 1);
    strcpy(double_s1, s1);
    strcat(double_s1, s1);
    int found = strstr(double_s1, s2) != NULL;
    free(double_s1);
    return found;
}

原理：s1 的所有旋轉變體都是 s1+s1 的子串。

對比總結