51nod 1304 字元串的相似度

題意

我們定義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

前言

很明顯地就是讓你求擴充KMP的f指針，全部加起來就是答案了

以前的時候，看到這題，隻會SAM，然後卡空間，覺得大毒瘤

今天講課的時候提了一下擴充KMP

然後發現很簡單QAQ

教程就不寫了。。

自己随便用筆畫一畫估計都能畫出來。。

CODE:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=;
char ss[N];
int len;
int f[N];
void get_f()
{
    f[]=len;
    int st=,ed=;
    for (int u=;u<=len;u++)
    {
        if (ed>=u)  f[u]=min(ed-u+,f[u-st+]);
        while (u+f[u]<=len&&ss[u+f[u]]==ss[f[u]+]) f[u]++;
        if (u+f[u]>=ed) {ed=u+f[u]-;st=u;}
    }
}
int main()  
{
    scanf("%s",ss+);len=strlen(ss+);
    get_f();
    long long ans=;
    for (int u=;u<=len;u++)    
        ans=ans+f[u];
    printf("%I64d\n",ans);
    return ;
}