题解:HDU6629 String Mathching

发布于 / 题解 / 0 条评论

本题为 2019 HDU Multi-University Training Contest 5 的 1007 题

题目传送门:🚪

Problem Description

String matching is a common type of problem in computer science. One string matching problem is as following:

Given a string S[0\cdots len−1], please calculate the length of the longest common prefix of S[i\cdots len−1] and S[0 \cdots len−1] for each i>0.

I believe everyone can do it by brute force.
The pseudo code of the brute force approach is as the following:

We are wondering, for any given string, what is the number of compare operations invoked if we use the above algorithm. Please tell us the answer before we attempt to run this algorithm.

input

The first line contains an integer T, denoting the number of test cases.
Each test case contains one string in a line consisting of printable ASCII characters except space.

  • 1 \leq T \leq 30

  • string length \leq 106 for every string

Output

For each test, print an integer in one line indicating the number of compare operations invoked if we run the algorithm in the statement against the input string.

Sample Input

 3
_Happy_New_Year_
ywwyww
zjczzzjczjczzzjc

Sample Output

17
7
32 

题意 & 算法

题目就是问题目中这个算法中比较的次数。题目中提及的算法就是暴力对串中每一个位置进行前缀匹配。我们可以推知,如果子串长度为 x ,我们就需要进行 x+1 次匹配(因为还有一次匹配失败的情况)。而如果我匹配的子串最后一位到达了原串的最后一位的话,我们只需要进行 x 次匹配(因为匹配失败的情况不会出现了)。所以这个问题就转换成了前缀匹配。扩展KMP算法就是为这种问题产生的。

KMP算法讲解传送门:🚪

这个题挺坑的,各种卡时间啊。卡memset()(其实也没必要用memset()),卡cin……T 了一晚上我才过去……

AC代码

#include <bits/stdc++.h>
using namespace std;
int nexts[1000006];
char T[1000006];
long long ans = 0;
void getNext(){
    int m = strlen(T);
    // m:T的长度
    int a = 0, p = 0;
    for (int i = 1; i < m; i++) {
        if (i >= p || i + nexts[i - a] >= p) {
            if (i >= p) p = i;
            while (p < m && T[p] == T[p - i])
                p++;
            nexts[i] = p - i;
            if(i + nexts[i] >= m)
                ans += nexts[i];
            else ans += nexts[i] + 1;
            a = i;
        }
        else{
            nexts[i] = nexts[i - a];
            if(i + nexts[i] >= m)
                ans += nexts[i];
            else ans += nexts[i] + 1;
        }
    }
}
int main(){
    int n;
    scanf("%d", &n);
    while(n--){
        scanf("%s", T);
        ans = 0;
        getNext();
        printf("%lld\n", ans);
    }
    return 0;
}
转载原创文章请注明,转载自: KONGJUNE » 题解:HDU6629 String Mathching
Not Comment Found