题目描述

我们定义2个字符串的相似度等于两个串的相同前缀的长度。例如 “abc” 同 “abd” 的相似度为2，”aaa” 同 “aaab” 的相似度为3。

给出一个字符串S，计算S同他所有后缀的相似度之和。例如：S = “ababaa”，所有后缀为：

ababaa 6

babaa 0

abaa 3

baa 0

aa 1

a 1

S同所有后缀的相似度的和 = 6 + 0 + 3 + 0 + 1 + 1 = 11

数据范围

1 <= L <= 1000000

=w=

原题求的是每个后缀与整个字符串的最长公共前缀的长度。

也即扩展KMP的next数组的值之和。

代码

#include<iostream>

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<algorithm>

#define ll long long

using namespace std;

const char* fin="ex1304.in";

const char* fout="ex1304.out";

const int inf=0x7fffffff;

const int maxn=1000007;

int n,i,j,k,limit,id;

ll ans;

char a[maxn];

int ne[maxn];

int main(){

    scanf("%s",a+1);

    n=strlen(a+1);

    limit=0;

    id=0;

    ne[1]=n;

    for (i=2;i<=n;i++){

        j=ne[i-id+1];

        if (i+j-1<limit) ne[i]=j;

        else{

            j=max(0,limit-i+1);

            for (;j+i<=n;j++) if (a[i+j]!=a[j+1]) break;

            if (i+j-1>limit){

                limit=i+j-1;

                id=i;

            }

            ne[i]=j;

        }

    }

    for (i=1;i<=n;i++) ans+=ne[i];

    printf("%lld",ans);

    return 0;

}