作业

字符串前缀和后缀的最大公共长度

前缀是指 不包括字符串最后一位的任意字符串 后缀是指 不包括字符串最开始一位的任意字符串

解析

abcdabd

子串	前缀	后缀	最大公共长度
a	a	a	0
ab	a	b	0
abc	a、ab	bc、c	0
abcd	a、ab、abc	bcd、cd、d	0
abcda	a、ab、abc、abcd	bcda、cda、da、a	1
abcdab	a、ab、abc、abcd、abcda	bcdab、cdab、dab、ab、b	2
abcdabd	a、ab、abc、abcd、abcda、abcdab	bcdabd、cdabd、dabd、abd、bd、d	0

代码

#include <stdio.h>
#include <string.h>

int StrEach[100];
int loadStrA(char *str,int len){
  StrEach[0] = 0;//
  int i=0,j=0;
  for(j = 1;j < len;j++){
    while(str[i]!=str[j]&&i>0){
      i = StrEach[i-1];
    }
    if(str[i]==str[j]){
      i++;
      StrEach[j] = i;
    }else{
      StrEach[j]=0;
    }
  }
}
int getStrLen(char *str){
  int i = 0;
  while(str[i++]);
  return i-1;
}

int main(){
  char *str="abcdabd";
  int len = getStrLen(str);
  loadStrA(str,len);
  for(int i =0;i<len;i++){
    printf("%d ",StrEach[i]);
  }
}

运行结果

//console
0 0 0 0 1 2 0