非kmp方法最后一个点wa
查看原帖
非kmp方法最后一个点wa
1048327
KANO07楼主2024/3/26 17:59

类似双指针的写法, 这个方法的正确性我也不太清楚,但我在本地对拍了很久都没有错误.我把i=j-1;去掉,用最朴素的暴力就是正确的答案. 请问i=j-1在哪些情况下会导致出错呢?

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int main()
{
	int n,ans;
	string a;
    cin>>n>>a;
    for(int i=1;i<n;i++){ //右起点 
        if(a[i]==a[0]){
            bool flag=1;
            int cnt = 0;//左起点 
            for(int j=i; j < n; j++){
                if(a[cnt]==a[j]) {
                    cnt++;
                    cnt %=i ;
                }
                else {
					flag=0; 
					i=j-1;
					break;
				}
            }
            if(flag) {
				ans=i;
				break;
			}
        }
    }
    if(ans==0)cout<<n<<endl;
    else cout<<ans<<endl;
    return 0; 
}
2024/3/26 17:59
加载中...