[已解决]重复子串

juhugufudu

（1）重复子串
读入一个字符串，求出这个字符串中重复次数最多的子串。例如，'ababab'中子串
'a','b','ab'均重复了三次。当然，'ababab'的子串'aba'相当于重复两次。
    问题就是上面的，谢谢啦~

最佳答案

月排行榜 / 总排行榜

人造人

2020-3-1 17:20:07

这个？

1. #include <stdio.h>
   
2. #include <string.h>
   
3. #include <stdbool.h>
   
4. 
   
5. bool search(const char *s, const char *e, char ch)
   
6. {
   
7.         while(s != e)
   
8.         {
   
9.                 if(*s == ch)
   
10.                         return true;
    
11.                 ++s;
    
12.         }
    
13.         return false;
    
14. }
    
15. 
    
16. size_t test_str(const char *str)
    
17. {
    
18.         size_t max = 0;
    
19.         size_t len = strlen(str);
    
20.         for(size_t i = 0; i < len; ++i)
    
21.         {
    
22.                 for(size_t j = i + 1; j < len; ++j)
    
23.                 {
    
24.                         if(search(str + i, str + j, str[j]))
    
25.                         {
    
26.                                 if(max < j - i)
    
27.                                         max = j - i;
    
28.                                 break;
    
29.                         }
    
30.                 }
    
31.         }
    
32.         return max;
    
33. }
    
34. 
    
35. int main(void)
    
36. {
    
37.         char buf[1024];
    
38.         scanf("%s", buf);
    
39.         printf("%lu\n", test_str(buf));
    
40.         return 0;
    
41. }
    

复制代码

跳转到最佳答案楼层

人造人

这个？

1. #include <stdio.h>
   
2. #include <string.h>
   
3. #include <stdbool.h>
   
4. 
   
5. bool search(const char *s, const char *e, char ch)
   
6. {
   
7.         while(s != e)
   
8.         {
   
9.                 if(*s == ch)
   
10.                         return true;
    
11.                 ++s;
    
12.         }
    
13.         return false;
    
14. }
    
15. 
    
16. size_t test_str(const char *str)
    
17. {
    
18.         size_t max = 0;
    
19.         size_t len = strlen(str);
    
20.         for(size_t i = 0; i < len; ++i)
    
21.         {
    
22.                 for(size_t j = i + 1; j < len; ++j)
    
23.                 {
    
24.                         if(search(str + i, str + j, str[j]))
    
25.                         {
    
26.                                 if(max < j - i)
    
27.                                         max = j - i;
    
28.                                 break;
    
29.                         }
    
30.                 }
    
31.         }
    
32.         return max;
    
33. }
    
34. 
    
35. int main(void)
    
36. {
    
37.         char buf[1024];
    
38.         scanf("%s", buf);
    
39.         printf("%lu\n", test_str(buf));
    
40.         return 0;
    
41. }
    

复制代码

te___amo

求出重复最多的单个字符？？

juhugufudu

te___amo 发表于 2020-3-1 18:58
求出重复最多的单个字符？？

多个字符

juhugufudu

人造人 发表于 2020-3-1 20:14
这个？

不是，这道题的子串可以是'aba'

人造人

juhugufudu 发表于 2020-3-2 13:01
不是，这道题的子串可以是'aba'

像上面那样，举一些例子
输入：
输出：

这样

dahua123333

magicpower

还好，不考虑时间复杂度，只考虑实现的话，大概需要两个函数：
第一个函数-发现字串：取任意一个n长字符串的首字符，然后从左往右位移，发现相同的，计数，发现不同的，记录为新子串，然后用字符串前两个字符进行位移，发现相同的，计数，发现不同的，记录为新子串，循环下去，直到子串长度为n

第二个函数：位移函数，固定总字符串，然后用子串从左往右位移匹配即可，代码有点长，不想写了

以上就是大概思路

magicpower

位移次数一定是总长n-子长k