최 장 답장 서브 문자열 알고리즘 (문자열 처리 문제 + 여러 가지 방법 으로 해결)
5857 단어 문자열 처리
회 문 은 바로 읽 고 거꾸로 읽 는 것 을 가리 키 는데, 결 과 는 abc ba 나 abba 와 같다.
제목 은 문자열 에서 가장 긴 답장 문자열 로 가 는 것 입 니 다.
1. 폭력 법
가장 쉽게 생각 나 는 것 은 폭력 적 인 해결 이다. 모든 꼬치 를 구하 고 답장 인지 아 닌 지 판단 해서 가장 긴 것 을 찾 는 것 이다.
각 하위 문자열 의 시간 복잡 도 O (N ^ 2) 를 구하 고 하위 문자열 이 회 문 O (N) 인지 아 닌 지 판단 하 며 둘 은 상승 관계 이기 때문에 시간 복잡 도 는 O (N ^ 3) 입 니 다.
string findLongestPalindrome(string &s)
{
int length=s.size();//
int maxlength=0;//
int start;//
for(int i=0;i<length;i++)//
for(int j=i+1;j<length;j++)//
{
int tmp1,tmp2;
for(tmp1=i,tmp2=j;tmp1<tmp2;tmp1++,tmp2--)//
{
if(s.at(tmp1)!=s.at(tmp2))
break;
}
if(tmp1>=tmp2&&j-i>maxlength)
{
maxlength=j-i+1;
start=i;
}
}
if(maxlength>0)
return s.substr(start,maxlength);//
return NULL;
}
2. 동적 기획
답장 문자열 의 하위 문자열 도 답장 입 니 다. 예 를 들 어 P [i, j] (i 로 j 로 끝 나 는 하위 문자열 을 표시 합 니 다) 는 답장 문자열 입 니 다. 그러면 P [i + 1, j - 1] 도 답장 문자열 입 니 다.이렇게 하면 가장 긴 회 문 자 열 은 일련의 열 문제 로 분 해 될 수 있다.이렇게 하면 추가 공간 O (N ^ 2) 가 필요 하고 알고리즘 복잡 도 역시 O (N ^ 2) 입 니 다.
우선 상태 방정식 과 전이 방정식 을 정의 합 니 다.
P [i, j] = 0 은 하위 문자열 [i, j] 이 답장 문자열 이 아니 라 는 것 을 나타 낸다. P [i, j] = 1 은 하위 문자열 [i, j] 이 답장 문자열 임 을 나타 낸다.
P[i,i]=1
P[i,j]｛=P[i+1,j-1],if(s[i]==s[j])
=0 ,if(s[i]!=s[j])
string findLongestPalindrome(string &s)
{
const int length=s.size();
int maxlength=0;
int start;
bool P[50][50]={false};
for(int i=0;i<length;i++)//
{
P[i][i]=true;
if(i<length-1&&s.at(i)==s.at(i+1))
{
P[i][i+1]=true;
start=i;
maxlength=2;
}
}
for(int len=3;len<length;len++)//
for(int i=0;i<=length-len;i++)//
{
int j=i+len-1;//
if(P[i+1][j-1]&&s.at(i)==s.at(j))
{
P[i][j]=true;
maxlength=len;
start=i;
}
}
if(maxlength>=2)
return s.substr(start,maxlength);
return NULL;
}
3. 중심 확장
중심 확장 은 주어진 문자열 의 모든 자 모 를 중심 으로 양쪽 으로 확장 하여 가장 긴 하위 문자열 을 찾 는 것 입 니 다. 알고리즘 복잡 도 는 O (N ^ 2) 입 니 다.
그러나 두 가지 상황 을 고려 해 야 한다.
1. aba 처럼 길이 가 홀수 입 니 다.
2. abba 를 생각 합 니 다. 이렇게 길 이 는 짝수 입 니 다.
string findLongestPalindrome(string &s)
{
const int length=s.size();
int maxlength=0;
int start;
for(int i=0;i<length;i++)//
{
int j=i-1,k=i+1;
while(j>=0&&k<length&&s.at(j)==s.at(k))
{
if(k-j+1>maxlength)
{
maxlength=k-j+1;
start=j;
}
j--;
k++;
}
}
for(int i=0;i<length;i++)//
{
int j=i,k=i+1;
while(j>=0&&k<length&&s.at(j)==s.at(k))
{
if(k-j+1>maxlength)
{
maxlength=k-j+1;
start=j;
}
j--;
k++;
}
}
if(maxlength>0)
return s.substr(start,maxlength);
return NULL;
}
4. Manacher 법
Manacher 법 은 aba 와 같은 길이 가 홀수 인 리 턴 문자열 만 해결 할 수 있 습 니 다. abba 와 같은 해결 할 수 없 기 때문에 그 안에 특수 문 자 를 추가 합 니 다. 저 는 '\#' 를 추가 하여 abba 를 a\# b\# b\# a 로 만 들 었 습 니 다. 이 알고리즘 은 이미 리 턴 문자열 의 대칭 성 을 이용 하여 계산 한 것 입 니 다. 구체 적 인 알고리즘 복잡 도 는 O (N) 입 니 다. 저 는 알 아 보지 못 했 습 니 다. 두 개의 포 함 된 for 순환 이 있 기 때 문 입 니 다.
구체 적 인 원 리 는 참고 여기, 이곳.
테스트 코드 에서 나 는 '\#' 를 걸 러 내지 않 았 다.
#define min(x, y) ((x)<(y)?(x):(y))
#define max(x, y) ((x)<(y)?(y):(x))
string findLongestPalindrome3(string s)
{
int length=s.size();
for(int i=0,k=1;i<length-1;i++)// #
{
s.insert(k,"#");
k=k+2;
}
length=length*2-1;// #
int *rad=new int[length]();
rad[0]=0;
for(int i=1,j=1,k;i<length;i=i+k)
{
while(i-j>=0&&i+j<length&&s.at(i-j)==s.at(i+j))
j++;
rad[i]=j-1;
for(k=1;k<=rad[i]&&rad[i-k]!=rad[i]-k;k++)// , rad[i-k]=rad[i]-k ， j=1
rad[i+k]=min(rad[i-k],rad[i]-k);
j=max(j-k,0);// j
}
int max=0;
int center;
for(int i=0;i<length;i++)
{
if(rad[i]>max)
{
max=rad[i];
center=i;
}
}
return s.substr(center-max,2*max+1);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
PHP 문자열 처리 10가지 간단한 방법이것은 쉼표와 구분된 문자열을 데이터로 변환해야 한다는 것을 의미합니다.만약 이 데이터가 처음에 데이터베이스에서 검색되었다면, 그것은 당신에게 하나의 그룹만 제공할 수 있을 것입니다.이 때 implode () 함수를...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
