90求条
查看原帖
90求条
1034698
jzy_CSPJ_AK楼主2024/11/23 15:31
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
string a, b;
int len1, len2;
vector<int>nxt(N);
void get_nxt(string s){//求模式串的nxt
    int lens = s.size();
    int i = 0, j = -1;nxt[0] = -1;
    while(i < lens){
        if(j == -1 || s[i] == s[j])++ i, ++ j, nxt[i] = j;//匹配成功
        else j = nxt[j];//失配,往回跳
    }
}
bool h(string s){
    int i = 0, j = s.length() - 1;
    while(i <= j){
        if(s[i] != s[j])return 0;
        i ++, j --;
    }
    return 1;
}
int main(){
    cin >> a;
    while(1){
        if(a == ".")return 0;
        nxt.clear();
        get_nxt(a);
        int k = nxt[a.length()];
        if(h(a))cout << a.length() << endl;
        else if(k == 0)cout << 1 << endl;
        else {
            if(2 * k <= a.length())cout << 1 << endl;
            else{
                if(a.length() % (a.length() - k) == 0) cout << a.length() / ( a.length() - k ) << endl;
                else cout << 1 << endl;
            }
        }
        cin >> a;
    }
    return 0;
}
2024/11/23 15:31
加载中...