Information
- ID
- 275
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 7
- Tags
- # Submissions
- 27
- Accepted
- 9
- Uploaded By
关键在于利用kmp的最大长度表,求出最长的重复子串,然后就可以求出最短不重复子串
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int N = 1e6+7;
int l;
string n;
ll ne[N];
int main()
{
cin>>l;
cin>>n;
for(ll i = 1,j = 0; i < l;i++){
while(j > 0&& n[i] != n[j])j = ne[j - 1];
if(n[i] == n[j])j++;
ne[i] = j;
}
cout<<l-ne[l - 1];
return 0;
}
By signing up a 追梦算法网 universal account, you can submit code and join discussions in all online judging services provided by us.