返回首页 - Notes - 2012

周期字符串问题


问题描述

输入一个长度不超过 80 个字符的字符串,该字符串会存在某些不断重复的子串,我们把该重复子串的长度称之为周期

要求编程输出该字符串的最小周期,如 abcabcabcabc,其周期可以说是 3,也可以说是 612,但要求输出的是其最小周期 3


解题思路

求解的关键在于,如何正确判断某个子串是否满足周期字符串的特征

这儿使用每个可能的周期值为外循环,然后在此基础上判断整个字符串是否符合以该周期值为周值的周期字符串特征

周期字符串有 word[i] == word[i%周期] 的特征,这是判断的关键所在

因为要求的是最小周期,所以一旦找到符合的就立即输出并结束循环


问题求解

C语言

#include <stdio.h>
#include <string.h>


int main (int argc, char* argv[]) {
    char word[81];

    scanf("%s", word);
    int len = strlen(word);

    // 可能的周期值范围为1到字符串的大小
    for (int i = 1; i <= len; ++i) {
        // 只对合法的有可能的周期进行判断
        if (len % i == 0) {
            // 周期字符串标志位,每判断一个新的可能周期值时设置为1
            int ok = 1;
            for (int j = i; j < len; ++j) {
                // 后续字符只要有一个不满足周期字符串的周期特征就将标志位置0,并跳出该轮循环
                if (word[j] != word[j%i]) {
                    ok = 0;
                    break;
                }
            }
            // 如果该轮循环的所有字符都满足周期特征,则立即输出并结束后续循环
            if (ok) {
                printf("%d\n", i);
                break;
            }
        }
    }

    return 0;
}

date : 2012-09-20、2014-11-24