图片说明
图片说明

  • 题意：
  • 扩展kmp的匹配次数。
  • 题解：
  • 扩展kmp就是：定义母串S和子串T，S的长度为n，T的长度为m；求 字符串T 与 字符串S的每一个后缀 的最长公共前缀；
  • 直接用模板写就行了
  • 代码：
    #include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
#define ll long long
const int MAX=1000010; //字符串长度最大值
int next1[MAX],extend[MAX];
char a[MAX],b[MAX];
//预处理计算Next数组
void getNext(char str[])
{
  int i=0,j,po,len=strlen(str);
  next1[0]=len; //初始化next[0]
  while(str[i]==str[i+1] && i+1<len) i++; next1[1]=i; //计算next[1]
  po=1; //初始化po的位置
  for(i=2;i<len;i++)
  {
      if(next1[i-po]+i < next1[po]+po) //第一种情况，可以直接得到next[i]的值
          next1[i]=next1[i-po];
      else //第二种情况，要继续匹配才能得到next[i]的值
      {
          j = next1[po]+po-i;
          if(j<0) j=0; //如果i>po+next[po],则要从头开始匹配
          while(i+j<len && str[j]==str[j+i]) j++; next1[i]=j;
          po=i; //更新po的位置
      }
  }
}
//计算extend数组
void EXKMP(char s1[],char s2[])
{
  int i=0,j,po,len=strlen(s1),l2=strlen(s2);
  getNext(s2); //计算子串的next数组
  while(s1[i]==s2[i] && i<l2 && i<len) i++; extend[0]=i;
  po=0; //初始化po的位置
  for(i=1;i<len;i++)
  {
      if(next1[i-po]+i < extend[po]+po) //第一种情况，直接可以得到extend[i]的值
          extend[i]=next1[i-po];
      else //第二种情况，要继续匹配才能得到extend[i]的值
      {
          j = extend[po]+po-i;
          if(j<0) j=0; //如果i>extend[po]+po则要从头开始匹配
          while(i+j<len && j<l2 && s1[j+i]==s2[j]) j++; extend[i]=j;
          po=i; //更新po的位置
      }
  }
}
int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
      memset(extend,0,sizeof(extend));
      memset(next1,0,sizeof(next1));
      ll sum = 0;
      scanf("%s",a);
      int l = strlen(a);
      strcpy(b,a);
      b[l] = '\0';
      EXKMP(a,b);
      for(int i=1;i<l;i++)
      {
          //cout<<extend[i]+1<<" ";
          sum += min((extend[i]+1),l-i);
      }
      //cout<<endl;
      cout<<sum<<endl;
  }
}