HDU - 3294 Girls' research (manacher 템 플 릿 문제)

제목 링크
제목 의 대의: 먼저 문자 ch 를 주 고 ch 는 'a' 임 을 나타 낸다. 이 를 통 해 문자 전환 정의 (즉, ch - 'a' 는 위상 차이 이 고 나머지 문 자 는 위상 차이 에 따라 이동 해 야 한다. 구체 적 으로 처리 하면 코드 를 볼 수 있다) 를 얻 고 소문 자로 구 성 된 문자열 을 주 며 문자열 의 자 모 를 모두 정의 에 따라 전환 시 키 고 마지막 으로 전 환 된 문자열 을 구 해 야 한다.최대 답장 문자열.
사고: 먼저 문자열 을 처리 한 다음 에 manacher 알고리즘 을 뛰 어 다 니 며 최대 답장 문자열 의 중심 위 치 를 기록 하면 됩 니 다. 관련 디 테 일 은 모두 코드 안에 있 습 니 다.

#include
#include
#include
#include
#include
#include
#include
#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define pi acos(-1)
typedef long long ll;
using namespace std;
#define INF 0x3f3f3f3f
const int MAX=2e5+10;

void manacher(string s)
{
	int len=s.size();
	string str="$#";
	for(int i=0;i<len;i++)
	{
		str+=s[i];
		str+='#';
	}
	int len2=2*len+1;
    int p[MAX*2];// p[i] str , i           
    int id=0,mx=0;
    int ans=-1;
	int index=-1;//index       ，       ，          
    for(int i=1;i<=len2;i++)
    {
        int left_i=2*id-i;//i  id     ，        
        if(i<mx) p[i]=min(p[left_i],mx-i);//         mx-i，   id    ,left_i   i 
        else p[i]=1;
        while(str[i-p[i]]==str[i+p[i]]) p[i]++;//    '\0'      
        if(mx<i+p[i])
        {
            id=i;
            mx=i+p[i];
        }   
        if(p[i]-1>ans)
		{
			ans=p[i]-1;
			index=i;
		}
    }
	if(ans<2) cout<<"No solution!"<<'
';
	//s  i    ， str  2*(i+1)
	//                   ok 
	else if(str[index]=='#')//index    
	{	
		int begin=index/2-ans/2;//                 
		cout<<begin<<' '<<begin+ans-1<<'
'<<s.substr(begin,ans)<<'
';
		//               
	}
	else
	{
		int begin=index/2-1-ans/2;
		cout<<begin<<' '<<begin+ans-1<<'
'<<s.substr(begin,ans)<<'
';
	}	
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);//        tle
    char trie[27]="abcdefghijklmnopqrstuvwxyz";//        
	char ch;
	string s;
	while(cin>>ch>>s)
	{
		int len=s.size();
		int ex=ch-'a';//   
		for(int i=0;i<len;i++)
		{
			s[i]=trie[(s[i]-'a'+26-ex)%26];//trie[25]=='z',  25     ，  %26，        
		}
		manacher(s);
	}
	system("pause");
	return 0;
}