KMP专题(三)

专题链接

• KMP专题(一)
• KMP专题(二)

HDU 3336 Count the string

题意：
事先说好，这题数据非常弱，典型的想的比出的简单，各种错误代码都能A。

这道题的题意是让你找出所有前缀在整个字符串中的子串数量。

思路：
这里只提供所谓出题人的思路，水水过去就算了啊。

对于一个位置，如果他的next数组不是0，说明这个后缀与前缀有匹配。注意这里是后缀，而不是在整个字符串范围内。然而这个思路还是A了。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <string>

using namespace std;

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary));

const int maxn = 2e5 + 5;
const int mod = 10007;

char des[maxn];
int nxt[maxn];
int len;

void getNext()
{
    int i = 0, j = -1;
    nxt[0] = -1;
    while (i < len)
        if (j == -1 || des[i] == des[j])
            nxt[++i] = ++j;
        else
            j = nxt[j];
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %s", &len, des);
        getNext();
        int ans = len;
        range(i, 1, len) if (nxt[i]) ans = (ans + 1) % mod;
        printf("%d\n", ans);
    }
    return 0;
}

HDU 4300 Clairewd’s message

题意：
还是还是还是还是还是还还是还是求最长相同前后缀的题。

思路：
无。

AC Code

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define ll long long
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))

const int maxn = 1e5 + 5;

char des[maxn], table[30], retable[30];
int nxt[maxn], len;

void getNext()
{
    int i = 0, j = -1;
    nxt[0] = -1;
    len = strlen(des);
    while (i < len) {
        if (j == -1 || table[des[i] - 'a'] == des[j])
            nxt[++i] = ++j;
        else
            j = nxt[j];
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%s %s", table, des);
        each(i, 26) retable[table[i] - 'a'] = 'a' + i;
        getNext();
        int crylen = len - nxt[len];
        crylen = crylen < (len + 1) / 2 ? (len + 1) / 2 : crylen;
        each(i, crylen) putchar(des[i]);
        each(i, crylen) putchar(retable[des[i] - 'a']);
        puts("");
    }
    return 0;
}

HDU 1238 Substrings

题意：
找出一个最长的字符串，使得它或他的反转是每个给定字符串的连续字串。

思路：
暴力枚举。

AC Code

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define ll long long
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))

const int inf = 0x3f3f3f3f;
const int maxn = 1e2 + 5;

int nxt[maxn], len;
char mat[maxn][maxn], des[maxn];

void getNext(const string& des)
{
    int i = 0, j = -1;
    nxt[0] = -1;
    len = des.length();
    while (i < len) {
        if (j == -1 || des[i] == des[j])
            nxt[++i] = ++j;
        else
            j = nxt[j];
    }
}

bool kmpMatch(const char* src, const string& des)
{
    int i = 0, j = 0, slen = strlen(src), dlen = des.length();
    getNext(des);
    while (i < slen && j < dlen) {
        if (j == -1 || src[i] == des[j])
            i++, j++;
        else
            j = nxt[j];
    }
    return j == dlen;
}

int main()
{
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int min_len = inf, max_len = 0;
        each(i, n) scanf("%s", mat[i]), min_len = min(min_len, (int)strlen(mat[i]));
        range(l, 1, min_len) range(s, 0, min_len - l)
        {
            string tmp = "", rtmp;
            range(i, s, s + l - 1) tmp += mat[0][i];
            rtmp = string(tmp.rbegin(), tmp.rend());
            bool flag = true;
            range(i, 1, n - 1) if (!kmpMatch(mat[i], tmp) && !kmpMatch(mat[i], rtmp))
            {
                flag = false;
                break;
            }
            if (flag)
                max_len = l;
        }
        printf("%d\n", max_len);
    }
    return 0;
}

HDU 2328 Corporate Identity

题意：
还是找出最长的公共连续子串。

思路：
暴力枚举。

AC Code

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define ll long long
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))

const int inf = 0x3f3f3f3f;
const int maxn = 2e2 + 5;

int nxt[maxn], len;
char mat[4010][maxn], des[maxn];

void getNext(const string& des)
{
    int i = 0, j = -1;
    nxt[0] = -1;
    len = des.length();
    while (i < len) {
        if (j == -1 || des[i] == des[j])
            nxt[++i] = ++j;
        else
            j = nxt[j];
    }
}

bool kmpMatch(const char* src, const string& des)
{
    int i = 0, j = 0, slen = strlen(src), dlen = des.length();
    getNext(des);
    while (i < slen && j < dlen) {
        if (j == -1 || src[i] == des[j])
            i++, j++;
        else
            j = nxt[j];
    }
    return j == dlen;
}

int main()
{
    int n;
    while (scanf("%d", &n) != EOF && n) {
        int min_len = inf;
        string ans = "";
        each(i, n) scanf("%s", mat[i]), min_len = min(min_len, (int)strlen(mat[i]));
        range(l, 1, min_len) range(s, 0, min_len - l)
        {
            string tmp = "";
            range(i, s, s + l - 1) tmp += mat[0][i];
            if (ans.length() == tmp.length() && ans < tmp)
                continue;
            bool flag = true;
            range(i, 1, n - 1) if (!kmpMatch(mat[i], tmp))
            {
                flag = false;
                break;
            }
            if (flag)
                ans = tmp;
        }
        if (ans.length() == 0)
            puts("IDENTITY LOST");
        else
            cout << ans << endl;
    }
    return 0;
}

小结

简单说一下，KMP可以解决的问题。

• 较高效的字符串匹配
• 较高效的字符串匹配计数
• 找最短循环节
• 找最长相同前后缀
• 累积的相同前后缀记录

主要是理解了next数组，一切好说。