poj 3376 Finding Palindromes

Finding Palindromes

http://poj.org/problem?id=3376

Time Limit: 10000MS   Memory Limit: 262144K
     
Case Time Limit: 2000MS

Description

A word is called a palindrome if we read from right to left is as same as we read from left to right. For example, "dad", "eye" and "racecar" are all palindromes, but "odd", "see" and "orange" are not palindromes.

Given n strings, you can generate n × n pairs of them and concatenate the pairs into single words. The task is to count how many of the so generated words are palindromes.

Input

The first line of input file contains the number of strings n. The following n lines describe each string:

The i+1-th line contains the length of the i-th string li, then a single space and a string of li small letters of English alphabet.

You can assume that the total length of all strings will not exceed 2,000,000. Two strings in different line may be the same.

Output

Print out only one integer, the number of palindromes.

Sample Input

3
1 a
2 ab
2 ba

Sample Output

5

Hint

The 5 palindromes are: 
aa aba aba abba baab

建立trie树

用原串的反串在trie树上匹配

假设反串匹配到i,trie树上到j

1、如果j是单词节点,即以j结尾的单词是反串的前缀,那么如果i以后(反串剩余的部分,不包括i)是回文串,以j结尾的单词都可以与匹配的单词构成回文串

2、如果反串匹配完了,即反串是以i结尾的单词的前缀,那么j后面(不包括j)有多少回文串,就可以产生多少合法答案

关键:字符串的前缀回文和后缀回文

用扩展kmp

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 2000008
using namespace std;
bool f[2][N];
long long ans;
char T[N],S[N];
int len,tot,root,id;
int st[N],ed[N],cnt;
int nxt[N],expand[N];
int trie[N][26],mark[N],sum[N];
void getnxt(char *s,int ll,int rr)
{
    int a=ll;
    nxt[0]=rr-ll+1;
    while(a+1<=rr && s[a]==s[a+1]) a++;
    nxt[1]=a-ll;
    a=1+ll;
    int p,l,j;
    for(int k=2+ll;k<=rr;k++)
    {
        p=a-ll+nxt[a-ll]-1; l=nxt[k-a];
        if(k-ll+l-1>=p)
        {
            j=p-k+ll+1>0 ? p-k+ll+1 : 0;
            while(k+j<=rr && s[k+j]==s[j+ll]) j++;
            nxt[k-ll]=j;
            a=k;
        }
        else nxt[k-ll]=l;
    }
}
void exkmp(char *s,char *t,int ll,int rr,int w)
{
    getnxt(t,ll,rr);
    int a=ll;
    while(a<=rr && s[a]==t[a]) a++;
    expand[0]=a-ll;
    a=ll;
    int p,l,j;
    for(int k=ll+1;k<=rr;k++)
    {
        p=a-ll+expand[a-ll]-1; l=nxt[k-a];
        if(k-ll+l-1>=p)
        {
            j=p-k+ll+1>0 ? p-k+ll+1 : 0;
            while(k+j<=rr && s[k+j]==t[j+ll]) j++;
            expand[k-ll]=j;
            a=k;
        }
        else expand[k-ll]=l;
    }
    for(int i=ll-ll;i<=rr-ll;i++)
     if(i+expand[i]==rr-ll+1) f[w][i+ll]=true;
}
void insert(int ll,int rr)
{
    root=0;
    for(int i=ll;i<=rr;i++)
    {
        id=S[i]-‘a‘;
        sum[root]+=f[0][i];
        if(!trie[root][id]) trie[root][id]=++tot;
        root=trie[root][id];
    }
    mark[root]++;
}
void find(int ll,int rr)
{
    root=0;
    for(int i=ll;i<=rr;i++)
    {
        id=T[i]-‘a‘;
        root=trie[root][id];
        if(!root) return;
        if(i!=rr&&f[1][i+1] || i==rr) ans+=mark[root];
    }
     ans+=sum[root];
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%s",&len,S+cnt);
        for(int j=0;j<len;j++) T[cnt+j]=S[cnt+len-j-1];
        st[i]=cnt;
        ed[i]=cnt+len-1;
        exkmp(S,T,st[i],ed[i],0);
        exkmp(T,S,st[i],ed[i],1);
        cnt+=len;
        insert(st[i],ed[i]);
    }
    for(int i=1;i<=n;i++)
     find(st[i],ed[i]);
    printf("%lld\n",ans);
}
时间: 06-17

poj 3376 Finding Palindromes的相关文章

POJ 2049 Finding Nemo 优先队列 STL

题目链接:http://poj.org/problem?id=2049 题目利用了<海底总动员>的情节,小丑鱼尼莫迷路了,他老爸去营救他便是题意. 题目给出了这样的地图,说是假设地图由墙和门组成,忽略墙的厚度,地图上有门,没有墙的地方是可以自由行动的问可以经过最少多少道门便可以营救到尼莫. 这个题给的数据是墙的交点为整数点,但鱼爸爸实在非墙的地方自由移动. 因此,这个题有两个难点: 1.如果建图保存地图 2.如何在地图上遍历 由于题目是给出一个点(x,y),来表示一段墙 我便用一对X,Y来表示

poj3376 KMP+字典树求回文串数量(n*n)

Finding Palindromes Time Limit: 10000MS   Memory Limit: 262144K Total Submissions: 4043   Accepted: 746 Case Time Limit: 2000MS Description A word is called a palindrome if we read from right to left is as same as we read from left to right. For exam

leetcode-longest palindromic substring-by 1337c0d3r

Given a string S, find the longest palindromic substring in S. Note:This is Part II of the article: Longest Palindromic Substring. Here, we describe an algorithm (Manacher’s algorithm) which finds the longest palindromic substring in linear time. Ple

POJ 2135 Farm Tour &amp;&amp; HDU 2686 Matrix &amp;&amp; HDU 3376 Matrix Again 费用流求来回最短路

累了就要写题解,最近总是被虐到没脾气. 来回最短路问题貌似也可以用DP来搞,不过拿费用流还是很方便的. 可以转化成求满流为2 的最小花费.一般做法为拆点,对于 i 拆为2*i 和 2*i+1,然后连一条流量为1(花费根据题意来定) 的边来控制每个点只能通过一次. 额外添加source和sink来控制满流为2. 代码都雷同,以HDU3376为例. #include <algorithm> #include <iostream> #include <cstring> #in

[ACM] POJ 3740 Easy Finding (DLX模板题)

Easy Finding Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 16178   Accepted: 4343 Description Given a M×N matrix A. Aij ∈ {0, 1} (0 ≤ i < M, 0 ≤ j < N), could you find some rows that let every cloumn contains and only contains one 1.

POJ 3740 Easy Finding

题目链接:http://poj.org/problem?id=3740 dancing links 入门题 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <string> 5 #include <iomanip> 6 using namespace std; 7 int M, N; 8 #define maxn 16*300+5 9 int R[

[ACM] POJ 3740 Easy Finding (DFS)

Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 16202   Accepted: 4349 Description Given a M×N matrix A. Aij ∈ {0, 1} (0 ≤ i < M, 0 ≤ j < N), could you find some rows that let every cloumn contains and only contains one 1. Input There a

poj 3740 -- Easy Finding (dfs)

题目大意:给出一个m行n列的数组,元素只有0和1, 问:能不能找出几行,使得每一列都有且仅有一个1. 分析:直接深搜即可 #include<iostream> #include<cstdio> using namespace std; int vis[311];//记录该列有1没 int n, m; int a[20][311]; bool flag; bool fuhe(int i){ for (int j = 1; j <= n; j++) if (a[i][j] &am

POJ 3740 Easy Finding DLX

题意:给你一个0,1矩阵 ,求精确覆盖 解题思路: DLX 解题代码: 1 // File Name: poj3740.cpp 2 // Author: darkdream 3 // Created Time: 2014年10月04日 星期六 20时06分31秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #i