https://codeforces.com/group/5yyKg9gx7m/contest/269717/problem/I
题目描述:
找出一个字符串s中,一串长度为k的字符串a,这个字符串a在s中只有一个。求出最大的k。
二分k即可。指定k,依次遍历字符串s中长度为k的字符串,就可以找出符合题意的最大k。
代码:
#include <iostream> #include <algorithm> #include <vector> #include <string.h> #include <map> using namespace std; typedef long long ll; int n; char s[106]; map<string,int> m; bool check(int k) { m.clear(); for(int i=0;i<n-k+1;i++) { char str[k+2]; strncpy(str,s+i,k); str[k]=‘\0‘; m[str]++; if(m[str]>1) return false; } return true; } int main() { cin>>n; cin>>s; int l=2; int r=n+1; int mid; while(l<r) { mid=l+(r-l)/2; if(check(mid)) r=mid; else { l=mid+1; mid++; } } if(n==1) mid=1; cout<<mid<<endl; return 0; }
原文:https://www.cnblogs.com/studyshare777/p/12405183.html