2 条题解

  • 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;
    }
    
    • 0
      @ 2025-10-8 16:56:01
      #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++) cin>>s1[i];
          memset(pre,0,sizeof(pre));
          for(int i=1,j=pre[i];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
      上传者