打印给定字符串的最长前缀，它也是C程序中同一字符串的后缀。

• Z时代
• 2024-01-10
• 分类：综合

给定一个字符串，我们必须检查最长前缀的长度，该长度也是字符串的后缀，例如，有一个字符串“ 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

以上是 打印给定字符串的最长前缀，它也是C程序中同一字符串的后缀。 的全部内容， 来源链接： utcz.com/z/341129.html