当前位置：首页 > article >正文

NOI / 1.7编程基础之字符串 30:字符环 c语言两次遍历解决循环

article 2024/9/23 7:30:10

描述

有两个由字符构成的环。请写一个程序，计算这两个字符环上最长连续公共字符串的长度。例如，字符串“ABCEFAGADEGKABUVKLM”的首尾连在一起，构成一个环；字符串“MADJKLUVKL”的首尾连在一起，构成一个另一个环；“UVKLMA”是这两个环的一个连续公共字符串。

输入

一行，包含两个字符串，分别对应一个字符环。这两个字符串之间用单个空格分开。字符串长度不超过255，且不包含空格等空白符。

输出

输出一个整数，表示这两个字符环上最长公共字符串的长度。

样例输入

ABCEFAGADEGKABUVKLM MADJKLUVKL

样例输出

#include <stdio.h>
#include <string.h>
#define N 260

// 将字符串s重复两次，例如将abc变为abcabc
void doubleArr(char s[]) {
    int len = strlen(s);
    for (int i = 0; i <= len; ++i)
        s[i + len] = s[i];
}

int MAX(int a, int b) {
    return a > b ? a : b;
}

int main() {
    char s1[N], s2[N];
    int i1 = 0, i2 = 0, l1, l2, mxLen = 0; // i1, i2分别是s1, s2的下标 mxLen:最大公共子串长度
    scanf("%s %s", s1, s2);
    l1 = strlen(s1);
    l2 = strlen(s2);
    doubleArr(s1); // 将字符串变为原字符串重复2遍，即为用一维数组表示环形数组
    doubleArr(s2);
    for (int i1 = 0; i1 < l1; ++i1)
        for (int i2 = 0; i2 < l2; ++i2) {
            int j = 0; // j为公共子串长度，最长也就是l1和l2的较小值
            while (j < l1 && j < l2) {
                if (s1[i1 + j] == s2[i2 + j])
                    j++;
                else
                    break;
            }
            mxLen = MAX(mxLen, j);
        }
    printf("%d", mxLen);
    return 0;
}

查看全文

http://www.kler.cn/news/149139.html