左神算法进阶班1_1添加最少字符得到原字符N次

2020-12-13 02:15

阅读：290

标签：Once 进阶 span delete add ble vector name 长度

Problem:
　　给定一个字符串str1，只能往str1的后面添加字符变成str2。

　　要求1：str2必须包含两个str1，两个str1可以有重合，但是不能以同一个位置开头。

　　要求2：str2尽量短最终返回str2

　　举例：

　　　　str1 = 123，str2 = 123123 时，包含两个str1，且不以相同位置开头，且str2最短。

　　　　str1 = 123123，str2 = 123123123 时，包含两个str1，且不以相同位置开头，且str2最短。

　　　　str1 = 111，str2 = 1111 时，包含两个str1，且不以相同位置开头，且str2最短。

Solution:
　　使用KMP算法；

　　求最后一个字符的后一个空位的最长相同前后缀长度，　然后将字符前面不属于相同部分添加N次就行

Code:

 1 #pragma once
 2 #include  3 #include  4 #include string>
 5 
 6 using namespace std;
 7 
 8 void getIndex(int*& index, string str)
 9 {
10     for (int i = 0, p = 0; i i)
11     {
12         if (i == 0)
13             index[i] = -1;
14         else if (i == 1)
15             index[i] = 0;
16         else
17         {
18             if (str[i - 1] == str[p])
19                 index[i] = ++p;
20             else if (p > 0)
21                 p = index[p];
22             else
23                 index[i] = 0;
24         }
25     }
26 }
27 
28 string addStr(string str, int N)
29 {
30     string res = str;
31     int* index = new int[str.size() + 1];
32     getIndex(index, str);//获取最长前后缀角标
33 
34     int L = str.length() - index[str.length()];//最后一个位置的前后缀长度
35     for (int i = 1; i i)
36     {
37         for (int j = 0; j j)
38             res += str[j];
39     }
40     delete[] index;
41     return res;
42 }
43 
44 
45 void Test()
46 {
47     string str;
48     str = "abcabc";
49     cout 3)  endl;
50 
51     str = "12345";
52     cout 2)  endl;
53 }

左神算法进阶班1_1添加最少字符得到原字符N次

标签：Once 进阶 span delete add ble vector name 长度

原文地址：https://www.cnblogs.com/zzw1024/p/11029620.html

上一篇：Java—System类入门学习

下一篇：关于写入Windows Log Event却没有任何记录的问题

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：左神算法进阶班1_1添加最少字符得到原字符N次
文章链接：http://soscw.com/index.php/essay/25169.html

亲，登录后才可以留言！

左神算法进阶班1_1添加最少字符得到原字符N次

评论

热门文章

推荐文章

最新文章

置顶文章