题目出自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