UESTC 1696 一道简单的字符串题 KMP+dp

一道简单的字符串题 KMP+dp

Source

2017 UESTC Training for Search Algorithm & String

UESTC 1696 一道简单的字符串题

My Solution

题意：求出所有前缀在字符串中出现次数的和

KMP+dp
dpi表示前缀s[0,i]在字符串中出现的次数，
根据next数组，从n向1跑。
u = i;
dp[u-1] += 1;
if(nxt[u]!=0) mod(dp[nxt[u]-1] += dp[u-1]);
ans = sigma{dpi}
时间复杂度 O(n)
空间复杂度 O(n)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 1e6 + 8;
const int MOD = 10007;

char pattern[MAXN];
int dp[MAXN];
inline void mod(int &x){
    x -= x / MOD * MOD;
}
int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    //freopen("a.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    //ios::sync_with_stdio(false); cin.tie(0);

    int n;
    scanf("%d%s", &n, pattern);
    vector nxt(n+1, 0);
    for(int i = 1, j = 0; i < n; i++){ j = i; while(j > 0){
            j = nxt[j];
            if(pattern[j] == pattern[i]){
                nxt[i + 1] = j + 1;
                break;
            }
        }
    }

    int i, u, ans = 0;
    for(i = n; i >= 1; i--){
        //cout <

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx