数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用C语言程序打印给定字符串的最长前缀，该前缀也是同一字符串的后缀。
给定一个字符串，我们需要检查最长前缀的长度，该前缀也是字符串的后缀，例如字符串“abcab”，这里“ab”长度为2，是具有相同前缀和后缀的最长子串。
示例
Input: str[] = { “aabbccdaabbcc” }
Output: 6
Input: abdab
Output: 2如果我们从字符串的开头和结尾开始指针，它们会在某个点重叠，所以与其这样做，不如从中间中断字符串，并开始匹配左右字符串。如果它们相等，则返回任何一个匹配字符串的大小，否则尝试两侧的较短长度。
算法
int longest(char str[], int n) START STEP 1 : DECLARE length AS 0 AND i AS n/2 STEP 2 : IF n < 2 THEN RETURN 1 STEP 3 :LOOP WHILE TILL str[i]!='\0' IF str[i] == str[length] THEN, INCREMENT length BY 1 INCREMENT i BY 1 ELSE IF length == 0 THEN, INCREMENT i BY 1 ELSE DECREMENT length BY 1 END IF END IF END WHILE RETURN length STOP
示例
#include <stdio.h>
int longest(char str[], int n){
int length = 0, i = n/2;
if( n < 2 )
return 1;
while( str[i]!='\0' ){
//When we find the character like prefix in suffix,
//we will move the length and i to count the length of the similar prefix and suffix
if (str[i] == str[length]){
++length;
++i;
} else //When prefix and suffix not equal{
if(length == 0)
++i;
else
--length;
}
}
return length;
}
int main(int argc, char const *argv[]){
char str[] = {"abccmmabcc"};
int n = sizeof(str)/sizeof(str[0]);
int length = longest(str, n);
printf("Length = %d", length);
return 0;
}输出
如果我们运行上述程序，它将生成以下输出
Length = 4
更新于：2019年8月22日
1K+ 次浏览
广告