串应用- 计算一个串的最长的真前后缀
时间: 2023-06-05 17:48:01 浏览: 85
串的最长真前后缀指的是一个字符串中既是前缀又是后缀的最长子串,但不能是整个字符串本身。计算一个串的最长真前后缀可以使用KMP算法,具体步骤如下:
1. 首先求出该串的next数组,next[i]表示以i结尾的子串的最长真前后缀长度。
2. 然后从后往前遍历next数组,找到第一个next[i]等于i的位置j,即为该串的最长真前后缀长度。
例如,对于字符串"ababab",其next数组为[,,1,2,3,4],因为以第4个字符结尾的子串"abab"的最长真前后缀为"ab",长度为2,而以第5个字符结尾的子串"ababa"的最长真前后缀为"aba",长度为3,以此类推。从后往前遍历next数组,发现第一个next[i]等于i的位置为j=2,即"abab"是该串的最长真前后缀,长度为4。
相关问题
c语言计算两个字符串的最长公共子串
要计算两个字符串的最长公共子串,可以使用动态规划的方法来实现。首先,创建一个二维数组来存储两个字符串中每个字符的比较结果。然后,遍历两个字符串,如果当前字符相同,就将二维数组中对应位置的值设为1,表示这两个字符相同;如果当前字符不同,就将对应位置的值设为0。
接下来,遍历二维数组,找出值为1的最大连续子数组,就是最长的公共子串。最后,将这个最长公共子串输出即可。
C语言代码示例:
```c
#include <stdio.h>
#include <string.h>
// 计算两个字符串的最长公共子串
void longestCommonSubstring(char *str1, char *str2) {
int len1 = strlen(str1);
int len2 = strlen(str2);
int dp[len1+1][len2+1];
int maxLen = 0;
int endPos = 0;
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (str1[i-1] == str2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
if (dp[i][j] > maxLen) {
maxLen = dp[i][j];
endPos = i;
}
}
}
}
char result[maxLen+1];
memcpy(result, &str1[endPos - maxLen], maxLen);
result[maxLen] = '\0';
printf("最长公共子串为:%s\n", result);
}
int main() {
char str1[] = "abcdxyz";
char str2[] = "xyzabcd";
longestCommonSubstring(str1, str2);
return 0;
}
```
这样就可以用C语言来计算两个字符串的最长公共子串了。
计算多个字符串中最长的字符串长度
可以使用循环遍历每个字符串并记录每个字符串的长度,然后找到其中的最大值。具体代码实现如下:
```
def longest_string_length(strings):
max_length = 0
for string in strings:
if len(string) > max_length:
max_length = len(string)
return max_length
```
调用该函数可以计算多个字符串中最长的字符串长度:
```
strings = ['abc', 'defgh', 'ijklmno']
max_length = longest_string_length(strings)
print(max_length) # 输出 7
```
请问您还有什么其他的问题吗?