引以为戒希望大家别像我CF的G T了一下午

namespace exKMP
{
    inline void Z(char *s, int n, int *z)
    {
        for (int i = 1; i <= n; i++)
            z[i] = 0;
        z[1] = n;
        for (int i = 2, l = 0, r = 0; i <= n; i++)
        {
            if (i <= r)
                z[i] = min(z[i - l + 1], r - i + 1);
            while (i + z[i] <= n && 1 + z[i] <= n && s[i + z[i]] == s[z[i] + 1])
                ++z[i];
            if (i + z[i] - 1 > r)
                l = i, r = i + z[i] - 1;
        }
    }

    inline void exkmp(char *s, int n, char *t, int m, int *z, int *p)
    {
        Z(t, m, z);
        for (int i = 1; i <= n; i++)
            p[i] = 0;
        for (int i = 1, l = 0, r = 0; i <= n; i++)
        {
            if (i <= r)
                p[i] = min(z[i - l + 1], r - i + 1);
            while (i + p[i] <= n && 1 + p[i] <= m && s[i + p[i]] == t[p[i] + 1])
                ++p[i];
            if (i + p[i] - 1 > r)
                l = i, r = i + p[i] - 1;
        }
    }
} // namespace exKMP