打印给定字符串的最长前缀,它也是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' ){ //当我们在后缀中找到像前缀这样的字符时, //我们将移动长度和i以计算相似的前缀和后缀的长度 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