[已解决]重复子串

juhugufudu

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

最佳答案

月排行榜 / 总排行榜

人造人

2020-3-1 17:20:07

这个？

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool search(const char *s, const char *e, char ch)
{
        while(s != e)
        {
                if(*s == ch)
                        return true;
                ++s;
        }
        return false;
}

size_t test_str(const char *str)
{
        size_t max = 0;
        size_t len = strlen(str);
        for(size_t i = 0; i < len; ++i)
        {
                for(size_t j = i + 1; j < len; ++j)
                {
                        if(search(str + i, str + j, str[j]))
                        {
                                if(max < j - i)
                                        max = j - i;
                                break;
                        }
                }
        }
        return max;
}

int main(void)
{
        char buf[1024];
        scanf("%s", buf);
        printf("%lu\n", test_str(buf));
        return 0;
}

跳转到最佳答案楼层

人造人

这个？

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool search(const char *s, const char *e, char ch)
{
        while(s != e)
        {
                if(*s == ch)
                        return true;
                ++s;
        }
        return false;
}

size_t test_str(const char *str)
{
        size_t max = 0;
        size_t len = strlen(str);
        for(size_t i = 0; i < len; ++i)
        {
                for(size_t j = i + 1; j < len; ++j)
                {
                        if(search(str + i, str + j, str[j]))
                        {
                                if(max < j - i)
                                        max = j - i;
                                break;
                        }
                }
        }
        return max;
}

int main(void)
{
        char buf[1024];
        scanf("%s", buf);
        printf("%lu\n", test_str(buf));
        return 0;
}

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