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:
#pragma once
#include <iostream>
#include <vector>
#include <string> using namespace std; void getIndex(int*& index, string str)
{
for (int i = , p = ; i <= str.length(); ++i)
{
if (i == )
index[i] = -;
else if (i == )
index[i] = ;
else
{
if (str[i - ] == str[p])
index[i] = ++p;
else if (p > )
p = index[p];
else
index[i] = ;
}
}
} string addStr(string str, int N)
{
string res = str;
int* index = new int[str.size() + ];
getIndex(index, str);//获取最长前后缀角标 int L = str.length() - index[str.length()];//最后一个位置的前后缀长度
for (int i = ; i < N; ++i)
{
for (int j = ; j < L; ++j)
res += str[j];
}
delete[] index;
return res;
} void Test()
{
string str;
str = "abcabc";
cout << addStr(str, ) << endl; str = "";
cout << addStr(str, ) << endl;
}