KMP专题(二)

专题链接

HUST 1010 The Minimum Length

题意：
找最小循环节长度。

思路：
无。

#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 = 1e6 + 5;
int len, nxt[maxn];
char des[maxn];

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()
{
    while (scanf("%s", des) != EOF) {
        len = strlen(des);
        getNext();
        printf("%d\n", len - nxt[len]);
    }
    return 0;
}

POJ 2406 Power Strings

题意：
找最短循环节……

思路：
无。

#include <cstring>
#include <iostream>
#include <cstdio>
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 = 1e6 + 5;
const int inf = 0x3f3f3f3f;
int nxt[maxn];
char src[maxn], des[maxn];
int slen, tlen;

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

int main()
{
    while (scanf("%s", des) != EOF) {
        if (des[0] == '.' && des[1] == '\0')
            break;
        tlen = strlen(des);
        getNext();
        int len = tlen - nxt[tlen];
        if (tlen % len == 0)
            printf("%d\n", tlen / len);
        else
            puts("1");
    }
    return 0;
}

POJ 2752 Seek the Name, Seek the Fame

题意：
计算所有前缀和后缀相同的字符串。

思路：
有点意思。这道题需要对 next 数组更深一层的了解。

AC Code

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

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)--)

typedef long long ll;

const int maxn = 4e5 + 10;
char str[maxn];
int nxt[maxn], ans[maxn];
int len, num;

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

int main()
{
    while (scanf("%s", str) != EOF) {
        len = strlen(str);
        getNext();
        while (len > 0) {
            ans[num++] = len;
            len = nxt[len];
        }
        rrange(i, 0, num - 1) printf("%d%c", ans[i], i ? ' ' : '\n');
    }
    return 0;
}

POJ 3080 Blue Jeans

题意：
给出多个字符串，找出最长的且字典序最小的公共连续子串。

思路：
数据很小，直接枚举第一个字符串的所有连续子串，再对其他 n-1 个字符串尝试匹配即可。

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)--)

const int maxn = 65;
char mat[15][maxn];
int nxt[maxn];

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

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

int main()
{
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        each(i, n) scanf("%s", mat[i]);
        string ans = "";
        range(l, 3, 60) range(s, 0, 60 - l)
        {
            string tmp = "";
            range(i, s, s + l - 1) tmp += mat[0][i];
            if (tmp.length() == ans.length() && tmp > ans)
                continue;
            bool flag = true;
            range(i, 1, n - 1) if (!kmpIndex(mat[i], tmp))
            {
                flag = false;
                break;
            }
            if (flag)
                ans = tmp;
        }
        if (ans.length() == 0)
            puts("no significant commonalities");
        else
            cout << ans << endl;
    }
    return 0;
}

HDU 2594 Simpsons’ Hidden Talents

题意：
给出两个字符串，找出最长的前缀与后缀相同的子串。

思路：
还是老思路，只要把两个字符串连接起来就可以了。但是有一个问题，就是匹配的时候可能会越界。
比如说 abab 与 ab 如果是直接连接起来，那么算法给出的结果将会是 ababab 。
一个行之有效的方法就是在中间加一个不会出现的字符，比如说 ‘ # ‘ ，’ & ‘ ，加上以后只有当两个字符串相同的才会出现越界情况。

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)--)

const int maxn = 5e4 + 5;

char s[maxn], des[maxn * 2];
int nxt[maxn * 2], len;

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

int main()
{
    while (scanf("%s", des) != EOF) {
        scanf("%s", s);
        strcat(des, "#");
        strcat(des, s);
        getNext();
        int ans = nxt[len];
        each(i, ans) putchar(des[i]);
        if (ans)
            putchar(' ');
        printf("%d\n", ans);
    }
    return 0;
}