【数据结构】串 - 习题

发布时间 2023-04-03 22:18:22作者: marshuni

就一道题,开摆了orz

习题

等值子串

【问题描述】如果字符串的一个子串(其长度大于1)的各个字符均相同,则称之为等值子串。试设计一算法,求出串S中一个长度最大的等值子串;如果串S 中不存在等值子串,则输出信息no

【输入形式】输入一个字符串,并以!结束

【输出形式】输出第一个出现的最长字符串,如果没有输出no

【样例输入】aabc123abc123cc!

【样例输出】aa

【样例输入】abceebccadddddaaadd!

【样例输出】ddddd

char dat[10086];
int main()
{
    // 输入部分
    int tmp=0;
    do
    {
        dat[tmp] = getchar();
    } while (dat[tmp++]!='!');

    // 处理部分
    // p指向当前处理到的位置。当然也可用int来替代,此时表示的是数组下标。
    // last变量存储上一个字符是什么,用于计数
    // cnt表示的是当前的连续字符数目(包含目前的字符);ans表示的是最大连续字符数
    // ansp指针指向达成最大连续字符的位置(一串连续字符的最后一个)
    char *p = dat;
    char last=0;
    int cnt,ans=0;
    char *ansp = NULL;
    do
    {
        // 如果当前字符和上一个一样,则计数器+1,否则归1
        if(*p==last)
            cnt++;
        else
            cnt=1;
        // 如果当前连续字符数刷新了记录,则标记位置
        // 不取等号是因为要求“第一个出现的最长字符串”
        if(ans<cnt)
        {
            ans = cnt;
            ansp = p;
        }
        last = *p;
    }
    while(*(p++)!='!');

    // 结果输出部分
    // 通过ans和ansp反推出最长字符串的起始位置
    p = ansp-ans+1;
    if(ans>1)
        for(int i=1;i<=ans;i++)
            putchar(*p);
    else
        printf("no");
    putchar('\n');
    return 0;
}