前言

OK，刷专题终于刷到了自己不会的最小表示法，在学习最小表示法之前，稍微总结一下。

kmp多水题，而且因为挂在hdu和poj上，本身有些数据也非常水，所以打算开个专题来汇总一下这些水题。

KMP专题链接

• KMP专题(一)
• KMP专题(三)

题解

HDU 1711 Number Sequence

题意：
返回第一个数字序列匹配的位置。

思路：
KMP入门题。

AC Code

#include <cstring>
#include <iostream>
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];
int 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]) {
            if (des[++i] != des[++j])
                nxt[i] = j;
            else
                nxt[i] = nxt[j];
        } else
            j = nxt[j];
}

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

int main()
{
    int T_T;
    scanf("%d", &T_T);
    while (T_T--) {
        scanf("%d %d", &slen, &tlen);
        each(i, slen)
            scanf("%d", src + i);
        each(i, tlen)
            scanf("%d", des + i);
        printf("%d\n", KMPIndex());
    }
    return 0;
}

HDU 1686 Oulipo

题意：
返回匹配数量。

思路
KMP入门题。

AC Code

#include <cstring>
#include <iostream>
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]) {
            if (des[++i] != des[++j])
                nxt[i] = j;
            else
                nxt[i] = nxt[j];
        } else
            j = nxt[j];
}

int KMPCount()
{
    int i, j = 0, ans = 0;
    if (slen == 1 && tlen == 1) {
        if (src[0] == des[0])
            return 1;
        else
            return 0;
    }
    getNext();
    for (i = 0; i < slen; i++) {
        while (j > 0 && src[i] != des[j])
            j = nxt[j];
        if (src[i] == des[j])
            j++;
        if (j == tlen) {
            ans++;
            j = nxt[j];
        }
    }
    return ans;
}

int main()
{
    int T_T;
    scanf("%d", &T_T);
    while (T_T--) {
        scanf("%s", des);
        scanf("%s", src);
        slen = strlen(src);
        tlen = strlen(des);
        printf("%d\n", KMPCount());
    }
    return 0;
}

HDU 2087 剪花布条

题意：
返回匹配数量，有点不一样的地方就是不能有重叠。比如说 aaaa 只能计作 两个 aa。

思路：
模板改一个小地方就好了。

AC Code

#include <cstring>
#include <iostream>
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]) {
            if (des[++i] != des[++j])
                nxt[i] = j;
            else
                nxt[i] = nxt[j];
        } else
            j = nxt[j];
}

int KMPCount()
{
    int i, j = 0, ans = 0;
    getNext();
    for (i = 0; i < slen; i++) {
        while (j > 0 && src[i] != des[j])
            j = nxt[j];
        if (src[i] == des[j])
            j++;
        if (j == tlen) {
            ans++;
            j = 0;
            //j = nxt[j];
        }
    }
    return ans;
}

int main()
{
    while (scanf("%s", src)) {
        if (src[0] == '#' && src[1] == '\0')
            break;
        scanf("%s", des);
        slen = strlen(src);
        tlen = strlen(des);
        printf("%d\n", KMPCount());
    }
    return 0;
}

HDU 3746 Cyclic Nacklace

当时第一次发现kmp的next数组的应用，简直惊为天人，立马写了一片博客……认为，恩，好题！

事实上这类题目，巨tm多……
博文链接

HDU 1358 Period

题意：
题目什么意思来着……

再看了一下题目，原来还是求循环节……对于每个位置都找一下循环节，如果刚好是完整的几个循环节而来，就输出这个位置和循环次数。

思路：
上面那篇懂了得话，这题也是水题。

AC Code

#include <cstring>
#include <iostream>
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()
{
    int cas = 0;
    while (scanf("%d", &tlen) && tlen) {
        scanf("%s", des);
        getNext();
        printf("Test case #%d\n", ++cas);
        for (int i = 2; i <= tlen; i++) {
            int len = i - nxt[i];
            if (i != len && i % len == 0)
                printf("%d %d\n", i, i / len);
        }
        puts("");
    }
    return 0;
}