1 条题解

  • 0
    @ 2026-3-19 13:19:17
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1110000;
    char sa[N], sb[N];
    int pre[N];
    
    int main() 
    {
        scanf("%s", sb+1);scanf("%s", sa+1);
        int lena=strlen(sa+1), lenb=strlen(sb+1);
        memset(pre, 0, sizeof(pre));
        for(int i=1, j=pre[i]; i<lena; i++, j=pre[i]) 
        {
            while( j>0 && sa[i+1]!=sa[j+1]) j=pre[j];
            if(sa[i+1]==sa[j+1])pre[i+1]=j+1;
        }
        int ans=0;
        for(int i=0, j=0; i<lenb; i++) 
        {
            while( j>0 && sb[i+1]!=sa[j+1]) j=pre[j];
            if(sb[i+1]==sa[j+1]) j++;
            if(j==lena) ans++;
        }
        printf("%d\n", ans);
    
        return 0;
    }
    
    
    • 1

    信息

    ID
    9892
    时间
    500ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    49
    已通过
    11
    上传者