1 条题解

  • 0
    @ 2025-10-8 16:56:09
    #include <bits/stdc++.h>
    using namespace std;
    int pre[11000];
    string s1[11000], s2[80];
    int main()
    {
        int n, m; scanf("%d%d", &n, &m);
        for(int i=1; i < n; i++, j=pre[i])
    	{
            while(j > 0 && s1[i+1] != s1[j+1]) j=pre[j];
            if(s1[i+1] == s1[j+1]) pre[i+1] = j+1;
        }
        int H = n - pre[n];
        for(int i=1; i <= m; i++) for(int j=1; j <= H; j++) s2[i] += s1[j][i-1];
        memset(pre, 0, sizeof(pre));
        for(int i=1, j=pre[i]; i < m; i++, j=pre[i])
    	{
            while(j > 0 && s2[i+1] != s2[j+1]) j=pre[j];
            if(s2[i+1] == s2[j+1]) pre[i+1] = j+1;
        }
        printf("%lld", 1ll * (m - pre[m]) * H);
        return 0;
    }
    
    • 1

    【KMP】重复矩阵[USACO03FALL] Milking Grid(数据加强版)

    信息

    ID
    1302
    时间
    1000ms
    内存
    64MiB
    难度
    4
    标签
    递交数
    72
    已通过
    33
    上传者