3034349_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX 1000001

using namespace std;

char str[MAX];
int left[MAX], right[MAX], len[MAX], pos[MAX], heap[MAX], ID[MAX], mark[MAX], LEN[MAX];
int lenth, cnt;

bool cmp(int a,int b)
{
	if(LEN[pos[a]]==LEN[pos[b]])
	{
		return pos[a] > pos[b];
	}
	else
	{
		return LEN[pos[a]] < LEN[pos[b]];
	}
}

int getMaxLen()
{
	int ret;

	while(cnt&&mark[pos[heap[0]]]==1)
	{
		pop_heap(heap,heap+cnt,cmp);
		cnt--;
	}
	if(cnt==0)
	{
		return -1;
	}
	ret = heap[0];
	pop_heap(heap,heap+cnt,cmp);
	cnt--;
	return ret;
}

int main()
{
	int i, j;
	int l, r;
	int p, id;
	char ch;

	scanf("%s",str);
	cnt = 0;
	lenth = strlen(str);
	left[0] = -1;
	memset(mark,0,sizeof(mark));
	for(i = 0; i < lenth; i++)
	{
		j = i;
		while(j<lenth&&str[j]==str[i])
			j++;
		heap[cnt] = cnt;
		pos[cnt] = i;
		right[j-1] = j;
		if(j!=lenth)
		{
			left[j] = j-1;
		}
		LEN[i] = len[i] = j-i;
		LEN[j-1] = len[j-1] = j-i;
		ID[i] = cnt;
		cnt++;
		i = j-1;
	}
	make_heap(heap,heap+cnt,cmp);
	while(1)
	{
		if(cnt<=0)
		{
			break;
		}
		id = getMaxLen();
		if(id==-1)
		{
			break;
		}
		p = pos[id];
		if(LEN[p]==1)
		{
			break;
		}
		ch = str[p];
		putchar(ch);
		l = left[p];
		while(1)
		{
			for(i = p; i < p+len[p]; i++)
			{
				printf(" %d",i+1);
			}
			p = right[i-1];
			if(p==lenth||str[p]!=ch)
			{
				break;
			}
		}
		r = right[p-1];
		printf("\n");
		mark[pos[id]] = 1;
		if(l!=-1&&r!=lenth)
		{
			right[l] = r;
			left[r] = l;
			if(str[l]==str[r])
			{
				mark[r] = 1;
				p = l-len[l]+1;
				LEN[p] += LEN[r];
				heap[cnt++] = ID[p];
				push_heap(heap,heap+cnt,cmp);
			}
		}
	}
	return 0;
}