Codeforces 427 D. Match & Catch
4159 단어 codeforces
두 열 중 유일하게 나타나는 최소 공통 문자열
D. Match & Catch
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output
Police headquarter is monitoring signal on different frequency levels. They have got two suspiciously encoded strings s1 and s2 from two different frequencies as signals. They are suspecting that these two strings are from two different criminals and they are planning to do some evil task.
Now they are trying to find a common substring of minimum length between these two strings. The substring must occur only once in the first string, and also it must occur only once in the second string.
Given two strings s1 and s2 consist of lowercase Latin letters, find the smallest (by length) common substring p of both s1 and s2, wherep is a unique substring in s1 and also in s2. See notes for formal definition of substring and uniqueness.
Input
The first line of input contains s1 and the second line contains s2 (1 ≤ |s1|, |s2| ≤ 5000). Both strings consist of lowercase Latin letters.
Output
Print the length of the smallest common unique substring of s1 and s2. If there are no common unique substrings of s1 and s2 print -1.
Sample test(s)
input
apple
pepperoni
output
2
input
lover
driver
output
1
input
bidhan
roy
output
-1
input
testsetses
teeptes
output
3
Note
Imagine we have string a = a1a2a3...a|a|, where |a| is the length of string a, and ai is the ith letter of the string.
We will call string alal + 1al + 2...ar (1 ≤ l ≤ r ≤ |a|) the substring [l, r] of the string a.
The substring [l, r] is unique in a if and only if there is no pair l1, r1 such that l1 ≠ l and the substring [l1, r1] is equal to the substring[l, r] in a.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10100,INF=0x3f3f3f3f;
int sa[maxn],rank[maxn],rank2[maxn],h[maxn],c[maxn],*x,*y,ans[maxn];
char str[maxn];
bool cmp(int*r,int a,int b,int l,int n)
{
if(r[a]==r[b]&&a+l<n&&b+l<n&&r[a+l]==r[b+l]) return true;
return false;
}
bool radix_sort(int n,int sz)
{
for(int i=0;i<sz;i++) c[i]=0;
for(int i=0;i<n;i++) c[x[y[i]]]++;
for(int i=1;i<sz;i++) c[i]+=c[i-1];
for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
}
void get_sa(char c[],int n,int sz=128)
{
x=rank,y=rank2;
for(int i=0;i<n;i++) x[i]=c[i],y[i]=i;
radix_sort(n,sz);
for(int len=1;len<n;len*=2)
{
int yid=0;
for(int i=n-len;i<n;i++) y[yid++]=i;
for(int i=0;i<n;i++) if(sa[i]>=len) y[yid++]=sa[i]-len;
radix_sort(n,sz);
swap(x,y);
x[sa[0]]=yid=0;
for(int i=1;i<n;i++)
{
x[sa[i]]=cmp(y,sa[i],sa[i-1],len,n)?yid:++yid;
}
sz=yid+1;
if(sz>=n) break;
}
for(int i=0;i<n;i++) rank[i]=x[i];
}
void get_h(char str[],int n)
{
int k=0; h[0]=0;
for(int i=0;i<n;i++)
{
if(rank[i]==0) continue;
k=max(k-1,0);
int j=sa[rank[i]-1];
while(i+k<n&&j+k<n&&str[i+k]==str[j+k]) k++;
h[rank[i]]=k;
}
}
int main()
{
cin>>str;
int sg=strlen(str);
str[sg]=127;
cin>>str+sg+1;
int n=strlen(str);
get_sa(str,n);
get_h(str,n);
int ans=INF;
int s1=0,s2=0,last=-1;
for(int i=1;i<n;i++)
{
if(sa[i-1]<sg&&sa[i]<sg) continue;
if(sa[i-1]>sg&&sa[i]>sg) continue;
int pre=h[i-1];
int next=h[i+1];
if(h[i]>max(pre,next))
{
ans=min(ans,max(pre,next)+1);
}
}
if(ans==INF) ans=-1;
printf("%d
",ans);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.