1 条题解

  • 0
    @ 2025-8-15 17:19:08
    #include<bits/stdc++.h>
    using namespace std;
    int dp[1000000];
    int len,j;
    string s;
    void read(int &h){
        char o;
        int x=0,y=1;
        o=getchar_unlocked();
        while(!(o<='9'&&o>='0')){
            if(o=='-'){
                y=-1;
            }
            o=getchar_unlocked();
        }
        while(o<='9'&&o>='0'){
            x*=10;
            x+=o-'0';
            o=getchar_unlocked();
        }
        h=x*y;
        return ;
    }
    int main() {
        read(len);
        cin>>s;
        s=" "+s;
        for (int i=1;i<len;i++) {
            while (j&&s[i+1]!=s[j+1]) {
                j=dp[j];
            }
            if (s[i+1]==s[j+1]) {
                j++;
            }
            dp[i+1]=j;
        }
        cout<<len-dp[len]<<endl;
        return 0;
    }
    
    
    
    • 1

    [BalticOI 2009] Radio Transmission 无线传输

    信息

    ID
    8418
    时间
    1000ms
    内存
    125MiB
    难度
    6
    标签
    递交数
    9
    已通过
    8
    上传者