HDU 3294マラアルゴリズム

2946 ワード
maacher
このアルゴリズムは,最後の列におけるいずれかのpos位置に対して,元の列の(pos−malache[pos]+2)/2−1位置に対応し,長さはmalache[pos]−1である.
これにより,すべての返信位置を直接求めることが容易になる.
テンプレートは前の文章のテンプレートを使っています
/*
#include 
#include 
#include 
#include 
using std::tr1::unordered_map;
*/

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

/*
   using std::sort;
   using std::bitset;
   using std::max;
   using std::cout;
   using std::stack;
   using std::cin;
   using std::endl;
   using std::swap;
   using std::pair;
   using std::vector;
   using std::set;
   using std::map;
   using std::multiset;
   using std::queue;
   using std::greater;
   using std::string;
   using std::priority_queue;
   using std::max_element;
   using std::min_element;

   using __gnu_pbds::pairing_heap_tag;
   __gnu_pbds::priority_queue, pairing_heap_tag> heap;
#define Hash unordered_map
*/
#define pr(x) cout<
	template
void manacher(T text[], int len, int malache[], T str[])  
{  
	T inf, space;
	if (typeid(T).name() == typeid(char).name())
	{
		inf= -128;
		space = 2 - 127;
	}
	if (typeid(T).name() == typeid(int).name())
	{
		inf= - 0x3f3f3f3f;
		space = 2 -0x3f3f3f3f;
	}
	int l = 0;
	str[l++] = inf;
	str[l++] = space;
	for (int i = 0; i < len; ++ i)
	{
		str[l++] = text[i];
		str[l++] = space;
	}
	str[l] = inf + 1;
	int mx=0, id=0;//mx:      ,id:            
	for (int i = 0; i < l; ++ i)
	{
		malache[i] = mx > i ? min(malache[2 * id - i], mx - i) : 1;
		while (str[i + malache[i]] == str[i - malache[i]])	malache[i] ++ ;
		if (i + malache[i] > mx)
		{
			mx = i + malache[i];
			id = i;
		}
	}  
}

char flag[10],input[400000 + 200];
int malache[400000 + 200];
char str[400000 + 200];

int main()
{
	while (scanf(" %s %s ", flag, input) == 2)
	{
		char ch = flag[0];
		int len = strlen(input);
		for (int i = 0; i != len; ++ i)
		{
			input[i] = (input[i]-ch+26)%26 + 'a';
		}
		manacher(input, len, malache, str);
		int pos=0, ans=0;
		for (int i = 0; i < 2 * len + 2; i ++)
		{
			if (malache[i]>ans)
			{
				ans = malache[i];
				pos = i;
			}
		}
		ans--;
		if (ans==1)
			printf("No solution!
");
		else
		{
			if (pos%2==0)
			{
				//     ，  pos/2-1   
				//pos-malache[pos]+1   
				//    (pos-malache[pos]+1)/2-1   ，  malache[pos]-1
				printf("%d %d
", (pos-malache[pos]+2)/2-1, (pos-malache[pos]+2)/2-1+ans-1);
			}
			else
			{
				//     ，    aa  baab      
				//(pos-malache[pos])/2   ，   malache[pos]-1
				printf("%d %d
", (pos-malache[pos]+2)/2-1, (pos-malache[pos]+2)/2-1+ans-1);
			}
			for (int i = (pos-malache[pos])/2; i <= (pos-malache[pos])/2 + ans - 1; ++ i)
				printf("%c", input[i]);
			printf("
");
		}
	}
}
ぜんはいち
RandomAccessインタフェースの使用