[BZOJ 3676] [APIO 2014] 댓 글 꼬치.

[제목 링크]
  • 클릭 하여 링크 열기
  • [아이디어 포인트]
  • 리 턴 트 리 템 플 릿 문제.

  • 시간 복잡 도
    【 코드 】
    #include
    using namespace std;
    #define MAXN	300005
    struct Palindromic_Tree {
    	int child[MAXN][26], father[MAXN];
    	int depth[MAXN], cnt[MAXN];
    	int size, last, len;
    	char s[MAXN];
    	int new_node(int length) {
    		memset(child[size], 0, sizeof(child[size]));
    		father[size] = 0;
    		depth[size] = length;
    		cnt[size] = 0;
    		return size++;
    	}
    	void Extend(int ch, int pos) {
    		int p = last;
    		while (s[pos - depth[p] - 1] != s[pos])
    			p = father[p];
    		if (!child[p][ch]) {
    			int now = new_node(depth[p] + 2), fa = father[p];
    			while (s[pos - depth[fa] - 1] != s[pos])
    				fa = father[fa];
    			father[now] = child[fa][ch];
    			if (father[now] == 0) father[now] = 1;
    			child[p][ch] = now;
    		}
    		last = child[p][ch];
    		cnt[last]++;
    	}
    	void init(char *x) {
    		len = strlen(x + 1);
    		for (int i = 1; i <= len; i++)
    			s[i] = x[i];
    		size = 0;
    		new_node(-1);
    		new_node(0);
    		father[0] = father[1] = 0;
    		depth[0] = -1;
    		last = 1;
    		for (int i = 1; i <= len; i++)
    			Extend(s[i] - 'a', i);
    	}
    	long long getans() {
    		long long ans = 0;
    		for (int i = size - 1; i > 0; i--) {
    			cnt[father[i]] += cnt[i];
    			ans = max(ans, (long long) cnt[i] * depth[i]);
    		}
    		return ans;
    	}
    } PT;
    char s[MAXN];
    int main() {
    	scanf("%s", s + 1);
    	PT.init(s);
    	printf("%lld
    ", PT.getans()); return 0; }

    좋은 웹페이지 즐겨찾기