2 条题解

  • 0
    @ 2025-10-8 16:58:52
    #include <bits/stdc++.h>
    using namespace std;
    const int N = 11100000;
    char s[N];
    int pre[N];
    int main() 
    {
        int n; scanf("%d%s", &n, s + 1);
        memset(pre, 0, sizeof(pre));
        for(int i = 1, j = pre[i]; i < n; i++, j = pre[i]) 
        {
            while(j > 0 && s[i + 1] != s[j + 1]) j = pre[j];
            if(s[i + 1] == s[j + 1]) pre[i + 1] = j + 1;     
        }
        printf("%d\n", n - pre[n]);
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:58:48
      #include<bits/stdc++.h>
      using namespace std;
      const int N=11100000;
      char s[N];
      int pre[N];
      int main() 
      {
      	int n; scanf("%d%s",&n,s+1);
          memset(pre,0,sizeof(pre));
          for(int i=1,j=pre[i]; i<n; i++,j=pre[i]) 
      	{
              while( j>0 && s[i+1]!=s[j+1]) j=pre[j];
              if(s[i+1]==s[j+1])pre[i+1]=j+1;     
          }
          printf("%d\n",n-pre[n]);
          return 0;
      }
      • 1

      *【KMP】字符串最小周期[BalticOI 2009]Radio Transmission

      信息

      ID
      1855
      时间
      1000ms
      内存
      512MiB
      难度
      5
      标签
      递交数
      45
      已通过
      18
      上传者