[C++] [ITSA竞赛题目][57-4] 寻找字串中最常出现的样板长度及内容

题目出自ITSA竞赛,解答仅供参考

题目连结: 寻找字串中最常出现的样板长度及内容

输入:

3QweTghJreDfeTQweTghJreDfeQweEsazFredQweqwdcBadcBadbdcBa

解答:

#include <stdio.h>#include <stdlib.h>#include <cstring>using namespace std;int search(char *str, int length, int start, int end);int main(void){    int n;    scanf("%d", &n);    while (n > 0)    {        char str[600];        int length = 0;        scanf("%s", str);        while (str[length] != '\0')        {            length++;        }        char styles[500][600]; //样式集合        int index = 0;         //样式集合的索引        int max = 0;           //最高次数        //for迴圈绕出所有样式        for (int i = 0; i < length - 1; i++)        {            for (int j = i + 1; j < length; j++)            {                //样式长度超过字串长度的一半                if (j - i + 1 > length / 2)                    continue;                                    int count = search(str, length, i, j);                if (count >= max)                {                    if (count > max)                    {                        //初始化样式集合                        index = 0;                        max = count;                    }                    //将样式加入样式集合                    int offset = 0;                    for (int k = i; k <= j; k++)                    {                        styles[index][offset] = str[k];                        offset++;                    }                    styles[index][offset] = '\0';                    index++;                }            }        }        //气泡排序        char temp[600];        for (int i = 0; i < index - 1; i++)        {            for (int j = i + 1; j < index; j++)            {                int offset = 0;                while (true)                {                    //前面字元小于后面字元,或前面字元先遇到结尾                    if (styles[i][offset] < styles[j][offset] ||                         styles[i][offset] == '\0')                    {                        break;                    }                    //后面字元小于前面字元,或后面字元先遇到结尾,交换位置                    if (styles[i][offset] > styles[j][offset] ||                         styles[j][offset] == '\0')                    {                        strcpy(temp, styles[i]);                        strcpy(styles[i], styles[j]);                        strcpy(styles[j], temp);                        break;                    }                    offset++;                }            }        }        //印出结果        printf("%d ", max);        for (int i = 0; i < index; i++)        {            if (i != 0)                printf(" ");            printf("%s", styles[i]);        }        printf("\n");        n--;    }    system("pause");    return 0;}//return 返回样式出现几次//str    字串//length 字串长度//start  要比对的样式的开始索引//end    要比对的样式的结束索引int search(char *str, int length, int start, int end){    int count = 0;    for (int i = start; i < length; i++)    {        //找到第一个符合的字元        if (str[i] == str[start])        {            bool isMatch = true;            int offset = 0;            for (int j = start; j <= end; j++)            {                //start到end之间只要有一个字元不符,或遇到结尾                if (str[i + offset] == '\0' || str[i + offset] != str[j])                {                    isMatch = false;                    break;                }                offset++;            }            if (isMatch)            {                count++;                //i加上比对的样式长度                i += offset - 1;            }        }    }    return count;}

说明:
先用 for 迴圈将样式绕出来,再丢进 search 函数算出样式在字串中出现的次数,中间跳过超过字串长度一半的样式,字串的绕法如下,以 abcdef 为例:
ab abc bc bcd cd cde de def ef

for (int i = start; i < length; i++)

search 函数内的第一个 for 迴圈 i 从 start 开始,因为我发现如果字串内有重覆的样式,例如 abab,会重覆搜寻 ab 两次并都返回2,main 取 max 时会取到重覆的样式,所以偷吃步把 i=0 改成 i=start,第二次的 ab 就会返回1而不是2,main 就不会取到重覆的样式,因为后面的次数一定会比前面的少。

i += offset - 1;

search 函数内 offset 的作用是,如果样式符合就要跳过整个样式,不重覆搜寻,样式与样式不重叠,例如 ababac 使用 aba 搜寻,会返回1而不是2,中间的 a 在第一次符合后就会因为 offset 而被跳过。

结语:
这题觉得没有写得很好,重覆的样式会被重覆搜寻,会造成效能上不必要的损耗,有想过在进入 search 函数之前先挡掉,不过后来不想增加阅读複杂度所以没有加,styles 阵列本来想做成动态的,后来因为要处理记忆体释放问题,程式变得很丑所以放弃用最原始写死的方式,这些都是可以继续优化的地方。
气泡排序那边本来写了一大堆程式处理字串调换,后来想到可以用 strcpy 来做,就变得很简洁 XD


关于作者: 网站小编

码农网专注IT技术教程资源分享平台,学习资源下载网站,58码农网包含计算机技术、网站程序源码下载、编程技术论坛、互联网资源下载等产品服务,提供原创、优质、完整内容的专业码农交流分享平台。

热门文章