[关闭]
@ivorysi 2018-01-02T08:28:32.000000Z 字数 30858 阅读 852

字符串学习笔记

笔记

KMP

POJ 2046 Power Strings

Description

Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n).

Input

Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

Output

For each s you should print the largest n such that s = a^n for some string a.

Sample Input

abcd
aaaa
ababab
.

Sample Output

1
4
3

题解

用扩展kmp做
求出next数组是原串i位置和第一个位置的最长公共前缀，从大到小枚举n（约数只有的级别）
然后暴力判断即可

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MAXN 1000005
  12. #define mod 1000000007
  13. //#define ivorysi
  14. using namespace std;
  15. typedef long long ll;
  16. ll read() {
  17.     ll res=0,neg=1;
  18.     char c=getchar();
  19.     while(c<'0' || c>'9') {
  20.     if(c=='-') neg=-1;
  21.     c=getchar();
  22.     }
  23.     while(c>='0' && c<='9') {
  24.     res=res*10+c-'0';
  25.     c=getchar();
  26.     }
  27.     return res*neg;
  28. }
  29. char s[MAXN];
  30. int next[MAXN],len;
  31. void solve() {
  32.     len=strlen(s+1);
  35.     memset(next,0,sizeof(next));
  36.     next[1]=len;
  37.     int pos=0,maxright=0;
  38.     siji(i,2,len) {
  39.     int z=next[i-pos+1];
  40.     if(i+z>maxright) {
  41.         z=max(0,maxright-i+1);
  42.         while(s[i+z]==s[z+1]) ++z;
  43.     }
  44.     next[i]=z;
  45.     if(i+z-1>maxright) {
  46.         maxright=i+z-1;
  47.         pos=i;
  48.     }
  49.     }
  50.     gongzi(i,len,2) {
  51.     if(len%i==0) {
  52.         int l=len/i;
  53.         bool flag=1;
  54.         xiaosiji(j,0,i) {
  55.         if(next[j*l+1]>=l) continue;
  56.         else  {flag=0;break;}
  57.         }
  58.         if(flag) {
  59.         printf("%d\n",i);
  60.         return;
  61.         }
  62.     }
  63.     }
  64.     puts("1");
  65. }
  66. int main() {
  67. #ifdef ivorysi
  68.     freopen("f1.in","r",stdin);
  69. #endif
  70.     while(1) {
  71.     scanf("%s",s+1);
  72.     if(s[1]=='.') break;
  73.     solve();
  74.     }
  75. }

codeforce 526D. Om Nom and Necklace

One day Om Nom found a thread with n beads of different colors. He decided to cut the first several beads from this thread to make a bead necklace and present it to his girlfriend Om Nelly.
Om Nom knows that his girlfriend loves beautiful patterns. That's why he wants the beads on the necklace to form a regular pattern. A sequence of beads S is regular if it can be represented as S = A + B + A + B + A + ... + A + B + A, where A and B are some bead sequences, " + " is the concatenation of sequences, there are exactly 2k + 1 summands in this sum, among which there are k + 1 "A" summands and k "B" summands that follow in alternating order. Om Nelly knows that her friend is an eager mathematician, so she doesn't mind if A or B is an empty sequence.
Help Om Nom determine in which ways he can cut off the first several beads from the found thread (at least one; probably, all) so that they form a regular pattern. When Om Nom cuts off the beads, he doesn't change their order.

Input

The first line contains two integers n, k (1 ≤ n, k ≤ 1 000 000) — the number of beads on the thread that Om Nom found and number k from the definition of the regular sequence above.
The second line contains the sequence of n lowercase Latin letters that represent the colors of the beads. Each color corresponds to a single letter.

Output

Print a string consisting of n zeroes and ones. Position i (1 ≤ i ≤ n) must contain either number one if the first i beads on the thread form a regular sequence, or a zero otherwise.
Examples

Input

7 2
bcabcab

Output

0000011

Input

21 2
ababaababaababaababaa

Output

000110000111111000011

题解

我们可以求出每个点和起点的最长公共前缀有多长，然后我们发现，每一个串必定是一些相等的区块A+B组成的，最后一个A是这个区块的一个前缀
然后我们枚举每一个A+B的长度l，k*l+1与第一位的最长公共前缀与l取个min，表示A能取的大小，这一段区间都是可以被切下来的
枚举长度和判断花费n/k*k=n的贡献，然后统计这些区间可以用差分，最后一次性更新，如果这个下标被覆盖过，那么这个下标就是可以从这里切断的

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <vector>
  6. #include <cmath>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 1000005
  11. //#define ivorysi 
  12. using namespace std;
  13. typedef long long ll;
  14. int readint() {
  15.     int res=0;
  16.     char c=getchar();
  17.     while(c<'0' || c>'9') {
  18.     c=getchar();
  19.     }
  20.     while(c>='0' && c<='9') {
  21.     res=res*10+c-'0';
  22.     c=getchar();
  23.     }
  24.     return res;
  25. }
  26. void out(ll x) {
  27.     if(x>=10) {
  28.     out(x/10);
  29.     }
  30.     putchar('0'+x%10);
  31. }
  32. int n,k;
  33. char s[MAXN];
  34. int next[MAXN];
  35. int ans[MAXN*5];
  36. void solve() {
  37.     n=readint();k=readint();
  38.     scanf("%s",s+1);
  39.     next[1]=n;
  40.     int pos=0,maxright=0;
  41.     siji(i,2,n) {
  42.     int j=next[i-pos+1];
  43.     if(i+j>=maxright) {
  44.         j=max(0,maxright-i+1);
  45.         while(s[i+j]==s[j+1]) {
  46.         ++j;
  47.         }
  48.     }
  49.     if(i+j-1>maxright) {
  50.         pos=i;
  51.         maxright=i+j-1;
  52.     }
  53.     next[i]=j;
  54.     }
  55.     siji(i,1,n) {
  56.     if(i<=n/k) {
  57.         bool flag=1;
  58.         int t=1;
  59.         siji(j,2,k) {
  60.         t+=i;
  61.         if(next[t]<i) {
  62.             flag=0;
  63.             break;
  64.         }
  65.         }
  66.         t+=i;
  67.         if(flag) {
  68.         int st=t-1,ed=t+min(next[t],i)-1;
  69.         ans[st]++;
  70.         ans[ed+1]--;
  71.         }
  72.     }
  73.     else {
  74.         break;
  75.     }
  76.     }
  77.     siji(i,1,n) {
  78.     ans[i]+=ans[i-1];
  79.     }
  80.     siji(i,1,n) {
  81.     if(ans[i]!=0) {
  82.         putchar('1');
  83.     }
  84.     else {
  85.         putchar('0');
  86.     }
  87.     }
  88.     putchar('\n');
  89. }
  90. int main() {
  91. #ifdef ivorysi
  92.     freopen("f1.in","r",stdin);
  93. #endif
  94.     solve();
  95. }

trie树

　POJ 2945 Find the Clones

Description

Doubleville, a small town in Texas, was attacked by the aliens. They have abducted some of the residents and taken them to the a spaceship orbiting around earth. After some (quite unpleasant) human experiments, the aliens cloned the victims, and released multiple copies of them back in Doubleville. So now it might happen that there are 6 identical person named Hugh F. Bumblebee: the original person and its 5 copies. The Federal Bureau of Unauthorized Cloning (FBUC) charged you with the task of determining how many copies were made from each person. To help you in your task, FBUC have collected a DNA sample from each person. All copies of the same person have the same DNA sequence, and different people have different sequences (we know that there are no identical twins in the town, this is not an issue).

Input

The input contains several blocks of test cases. Each case begins with a line containing two integers: the number 1 ≤ n ≤ 20000 people, and the length 1 ≤ m ≤ 20 of the DNA sequences. The next n lines contain the DNA sequences: each line contains a sequence of m characters, where each character is either A',C', G' orT'.
The input is terminated by a block with n = m = 0 .

Output

For each test case, you have to output n lines, each line containing a single integer. The first line contains the number of different people that were not copied. The second line contains the number of people that were copied only once (i.e., there are two identical copies for each such person.) The third line contains the number of people that are present in three identical copies, and so on: the i -th line contains the number of persons that are present in i identical copies. For example, if there are 11 samples, one of them is from John Smith, and all the others are from copies of Joe Foobar, then you have to print 1' in the first andthe tenth lines, and0' in all the other lines.

Sample Input

9 6
AAAAAA
ACACAC
GTTTTG
ACACAC
GTTTTG
ACACAC
ACACAC
TCCCCC
TCCCCC
0 0

Sample Output

1
2
0
1
0
0
0
0
0

Hint

Huge input file, 'scanf' recommended to avoid TLE.

题解

建一个trie树然后深搜
找到对应深度的地方然后，然后累加到ans上

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MAXN 400005
  12. #define mod 1000000007
  13. //#define ivorysi
  14. using namespace std;
  15. typedef long long ll;
  16. ll read() {
  17.     ll res=0,neg=1;
  18.     char c=getchar();
  19.     while(c<'0' || c>'9') {
  20.     if(c=='-') neg=-1;
  21.     c=getchar();
  22.     }
  23.     while(c>='0' && c<='9') {
  24.     res=res*10+c-'0';
  25.     c=getchar();
  26.     }
  27.     return res*neg;
  28. }
  29. struct node {
  30.     int to,next;
  31.     char val;
  32. }edge[MAXN];
  33. char s[MAXN];
  34. int n,m;
  35. int head[MAXN],sumedge,nodecnt=1,cnt[MAXN],ans[MAXN];
  36. void add(int u,int v,char c) {
  37.     edge[++sumedge].to=v;
  38.     edge[sumedge].next=head[u];
  39.     edge[sumedge].val=c;
  40.     head[u]=sumedge;
  41. }
  42. void ins() {
  43.     int p=1;
  44.     siji(k,1,m) {
  45.     bool flag=0;
  46.     for(int i=head[p];i;i=edge[i].next) {
  47.         int v=edge[i].to;
  48.         if(edge[i].val==s[k]) {
  49.         p=v;
  50.         flag=1;
  51.         break;
  52.         }
  53.         }
  54.     if(!flag) {
  55.         add(p,++nodecnt,s[k]);
  56.         p=nodecnt;
  57.     }
  58.     }
  59.     ++cnt[p];
  60. }
  61. void dfs(int u,int dep) {
  62.     if(dep==m) {
  63.     ans[cnt[u]]++;
  64.     }
  65.     for(int i=head[u];i;i=edge[i].next) {
  66.     int v=edge[i].to;
  67.     dfs(v,dep+1);
  68.     }
  69. }
  70. void solve() {
  71.     sumedge=0;
  72.     nodecnt=1;
  73.     memset(head,0,sizeof(head));
  74.     memset(ans,0,sizeof(ans));
  75.     memset(cnt,0,sizeof(cnt));
  76.     siji(i,1,n) {
  77.     scanf("%s",s+1);
  78.     ins();
  79.     }
  80.     dfs(1,0);
  81.     siji(i,1,n) {
  82.     printf("%d\n",ans[i]);
  83.     }
  84. }
  85. int main() {
  86. #ifdef ivorysi
  87.     freopen("f1.in","r",stdin);
  88. #endif
  89.     while(1) {
  90.     n=read();m=read();
  91.     if(n==0 && m==0) break;
  92.     solve();
  93.     }
  94. }

Wild Words

Description

A word is a string of lowercases. A word pattern is a string of lowercases, '?'s and ''s. In a pattern, a '?' matches any single lowercase, and a '' matches none or more lowercases.
There are many word patterns and some words in your hand. For each word, your task is to tell which patterns match it.

Input

The first line of input contains two integers N (0 < N <= 100000) and M (0 < M <=100), representing the number of word patterns and the number of words. Each of the following N lines contains a word pattern, assuming all the patterns are numbered from 0 to N-1. After those, each of the last M lines contains a word.
You can assume that the length of patterns will not exceed 6, and the length of words will not exceed 20.

Output

For each word, print a line contains the numbers of matched patterns by increasing order. Each number is followed by a single blank. If there is no pattern that can match the word, print "Not match".

Sample Input

5 4
t*
?h*s
??e*
*s
?*e
this
the
an
is

Sample Output

0 1 3
0 2 4
Not match
3

题解

好像大多数人都是拿模糊串做的匹配……而我是拿要询问的那些串来建一棵trie树，然后跑上面的模式串
为了剪枝开了一个记忆化搜索，貌似因为开得有点大每次清空的时候导致T，然后把数组改成了规范的样子
有一个地方错了

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 2005
  11. #define mod 1000000007
  12. //#define ivorysi
  13. using namespace std;
  14. typedef long long ll;
  15. ll read() {
  16.     ll res=0,neg=1;
  17.     char c=getchar();
  18.     while(c<'0' || c>'9') {
  19.         if(c=='-') neg=-1;
  20.         c=getchar();
  21.     }
  22.     while(c>='0' && c<='9') {
  23.         res=res*10+c-'0';
  24.         c=getchar();
  25.     }
  26.     return res*neg;
  27. }
  28. struct node {
  29.     int to,next;
  30.     char val;
  31. }edge[MAXN*2];
  33. int head[MAXN],sumedge,pos[MAXN],nodecnt=1,fa[MAXN];
  34. vector<int> ans[105];
  35. int n,m;
  36. char str[100005][10],s[25];
  37. int getfa(int x) {
  38.     return x==fa[x]? x:fa[x]=getfa(fa[x]);
  39. }
  40. void add(int u,int v,char c) {
  41.     edge[++sumedge].to=v;
  42.     edge[sumedge].val=c;
  43.     edge[sumedge].next=head[u];
  44.     head[u]=sumedge;
  45. }
  46. void ins(int x) {
  47.     int l=strlen(s+1);
  48.     int p=1;
  49.     siji(k,1,l) {
  50.         bool flag=0;
  51.         for(int i=head[p];i;i=edge[i].next) {
  52.             int v=edge[i].to;
  53.             if(edge[i].val==s[k]) {
  54.                 p=v;
  55.                 flag=1;
  56.                 break;
  57.             }
  58.         }
  59.         if(!flag) {
  60.             add(p,++nodecnt,s[k]);
  61.             p=nodecnt;
  62.         }
  63.     }
  64.     if(pos[p]!=0) fa[getfa(x)]=getfa(pos[p]);
  65.     else pos[p]=x;
  66. }
  67. int now,len;
  68. bool used[MAXN][15];
  69. void dfs(int u,int p) {
  70.     if(used[u][p]) {
  71.         return;
  72.     }
  73.     used[u][p]=1;
  74.     if(pos[u]!=0 && p==len) {
  75.         ans[pos[u]].push_back(now);
  76.     }
  77.     if(p!=len && s[p+1]=='*') dfs(u,p+1);
  78.     for(int i=head[u];i;i=edge[i].next) {
  79.         int v=edge[i].to;
  80.         if(p!=len && (edge[i].val==s[p+1] || s[p+1]=='?')) {
  81.             dfs(v,p+1);
  82.         }
  83.         if(p!=0 && s[p]=='*') {//这里不能写else因为这种情况一定要搜索一下
  84.             dfs(v,p);
  85.         }
  86.     }
  87. }
  88. void solve() {
  89.     n=read();m=read();
  90.     siji(i,1,n) {
  91.         scanf("%s",str[i]+1);
  92.     }
  93.     siji(i,1,m) {
  94.         fa[i]=i;
  95.         scanf("%s",s+1);
  96.         ins(i);
  97.     }
  98.     siji(i,1,n) {
  99.         now=i;
  100.         strcpy(s+1,str[i]+1);
  101.         len=strlen(str[i]+1);
  102.         /*int cnt=0;
  103.         bool flag=0;
  104.         int l=strlen(str[i]+1);
  105.         siji(j,1,l) {
  106.             if(str[i][j]!='?' && str[i][j]!='*') {
  107.                 siji(k,1,cnt) {
  108.                     s[++len]='?';
  109.                 }
  110.                 if(flag) s[++len]='*';
  111.                 s[++len]=str[i][j];
  112.                 flag=0;cnt=0;
  113.             }
  114.             else if(str[i][j]=='?') {
  115.                 ++cnt;
  116.             }
  117.             else if(str[i][j]=='*') {
  118.                 flag=1;
  119.             }
  120.         }
  121.         siji(i,1,cnt) s[++len]='?';
  122.         if(flag) s[++len]='*';*/
  123.         memset(used,0,sizeof(used));
  124.         dfs(1,0);
  125.     }
  126.     siji(i,1,m) {
  127.         int t=getfa(i);
  128.         int s=ans[t].size();
  129.         if(s==0) {
  130.             puts("Not match");
  131.         }
  132.         else {
  134.             xiaosiji(j,0,s) {
  135.                 printf("%d ",ans[t][j]-1);
  136.             }
  137.             puts("");
  138.         }
  140.     }
  141. }
  142. int main() {
  143. #ifdef ivorysi
  144.     freopen("f1.in","r",stdin);
  145. #endif
  146.     solve();
  148. }

codeforce 633 C. Spy Syndrome 2

After observing the results of Spy Syndrome, Yash realised the errors of his ways. He now believes that a super spy such as Siddhant can't use a cipher as basic and ancient as Caesar cipher. After many weeks of observation of Siddhant’s sentences, Yash determined a new cipher technique.
For a given sentence, the cipher is processed as:
Convert all letters of the sentence to lowercase.
Reverse each of the words of the sentence individually.
Remove all the spaces in the sentence.
For example, when this cipher is applied to the sentence

Kira is childish and he hates losing

the resulting string is

ariksihsidlihcdnaehsetahgnisol

Now Yash is given some ciphered string and a list of words. Help him to find out any original sentence composed using only words from the list. Note, that any of the given words could be used in the sentence multiple times.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 10 000) — the length of the ciphered text. The second line consists of n lowercase English letters — the ciphered text t.
The third line contains a single integer m (1 ≤ m ≤ 100 000) — the number of words which will be considered while deciphering the text. Each of the next m lines contains a non-empty word wi (|wi| ≤ 1 000) consisting of uppercase and lowercase English letters only. It's guaranteed that the total length of all words doesn't exceed 1 000 000.

Output

Print one line — the original sentence. It is guaranteed that at least one solution exists. If there are multiple solutions, you may output any of those.

Examples

Input

30
ariksihsidlihcdnaehsetahgnisol
10
Kira
hates
is
he
losing
death
childish
L
and
Note

Output

Kira is childish and he hates losing

Input

12
iherehtolleh
5
HI
Ho
there
HeLLo
hello

Output

HI there HeLLo

Note

In sample case 2 there may be multiple accepted outputs, "HI there HeLLo" and "HI there hello" you may output any of them.

题解

把每个字符串取反存字典树，然后dp[n]表示能否匹配到n，同时记录一下用的是第几个串还有从哪个位置匹配过来的

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MAXN 10005
  12. #define MAXM 100005
  13. #define mod 1000000007
  14. //#define ivorysi
  15. using namespace std;
  16. typedef long long ll;
  17. ll read() {
  18.     ll res=0,neg=1;
  19.     char c=getchar();
  20.     while(c<'0' || c>'9') {
  21.     if(c=='-') neg=-1;
  22.     c=getchar();
  23.     }
  24.     while(c>='0' && c<='9') {
  25.     res=res*10+c-'0';
  26.     c=getchar();
  27.     }
  28.     return res*neg;
  29. }
  30. struct node {
  31.     int to,next;
  32.     char val;
  33. }edge[1000005];
  34. int head[1000005],sumedge,nodecnt=1;
  35. void add(int u,int v,char c) {
  36.     edge[++sumedge].to=v;
  37.     edge[sumedge].next=head[u];
  38.     edge[sumedge].val=c;
  39.     head[u]=sumedge;
  40. }
  41. int n,m;
  42. int pos[MAXM],len[MAXM],isend[1000005];
  43. int id[MAXN],from[MAXN],ans[MAXN],tot;
  44. bool dp[MAXN];
  45. char str[MAXN];
  46. char s[1000005];
  47. void ins(int x) {
  48.     int p=1;
  49.     gongzi(i,len[x],1) {
  50.     char t=s[pos[x]+i-1];
  51.     if(t>='A' && t<='Z') t='a'+t-'A';
  52.     bool flag=0;
  53.     for(int l=head[p];l;l=edge[l].next) {
  54.         int z=edge[l].to;
  55.         if(edge[l].val==t) {
  56.         p=z;
  57.         flag=1;
  58.         break;
  59.         }
  60.     }
  61.     if(!flag) {
  62.         add(p,++nodecnt,t);
  63.         p=nodecnt;
  64.     }
  65.     }
  66.     if(!isend[p]) {
  67.     isend[p]=x;
  68.     }
  69. }
  70. int find(int st,int ed) {
  71.     int p=1;
  72.     siji(i,st,ed) {
  73.     bool flag=0;
  74.     for(int l=head[p];l;l=edge[l].next) {
  75.         int z=edge[l].to;
  76.         if(edge[l].val==str[i]) {
  77.         p=z;
  78.         flag=1;
  79.         break;
  80.         }
  81.     }
  82.     if(!flag) return -1;
  83.     }
  84.     if(!isend[p]) return -1;
  85.     else return isend[p];
  86. }
  87. void solve() {
  88.     n=read();
  89.     scanf("%s",str+1);
  90.     m=read();
  91.     pos[1]=1;
  92.     scanf("%s",s+1);
  93.     len[1]=strlen(s+1);
  94.     siji(i,2,m) {
  95.     pos[i]=len[i-1]+pos[i-1];
  96.     scanf("%s",s+pos[i]);
  97.     len[i]=strlen(s+pos[i]);
  98.     }
  99.     siji(i,1,m) {
  100.     ins(i);
  101.     }
  102.     dp[0]=1;
  103.     siji(i,1,n) {
  104.     int st=max(0,i-1000);
  105.     gongzi(j,i-1,st) {
  106.         if(dp[j]) {
  107.         int x=find(j+1,i);
  108.         if(x!=-1) {
  109.             dp[i]=1;
  110.             id[i]=x;
  111.             from[i]=j;
  112.             break;
  113.         }   
  114.         }
  115.     }
  116.     }
  117.     int t=n;
  118.     while(t!=0) {
  119.     ans[++tot]=id[t];
  120.     t=from[t];
  121.     }
  122.     gongzi(i,tot,1) {
  123.     siji(k,pos[ans[i]],pos[ans[i]]+len[ans[i]]-1) {
  124.         putchar(s[k]);
  125.     }
  126.     putchar(' ');
  127.     }
  128.     putchar('\n');
  129. }
  130. int main() {
  131. #ifdef ivorysi
  132.     freopen("f1.in","r",stdin);
  133. #endif
  134.     solve();
  137. }

POJ 1204 Word Puzzles

Description

Word puzzles are usually simple and very entertaining for all ages. They are so entertaining that Pizza-Hut company started using table covers with word puzzles printed on them, possibly with the intent to minimise their client's perception of any possible delay in bringing them their order.
Even though word puzzles may be entertaining to solve by hand, they may become boring when they get very large. Computers do not yet get bored in solving tasks, therefore we thought you could devise a program to speedup (hopefully!) solution finding in such puzzles.
The following figure illustrates the PizzaHut puzzle. The names of the pizzas to be found in the puzzle are: MARGARITA, ALEMA, BARBECUE, TROPICAL, SUPREMA, LOUISIANA, CHEESEHAM, EUROPA, HAVAIANA, CAMPONESA.
Your task is to produce a program that given the word puzzle and words to be found in the puzzle, determines, for each word, the position of the first letter and its orientation in the puzzle.
You can assume that the left upper corner of the puzzle is the origin, (0,0). Furthemore, the orientation of the word is marked clockwise starting with letter A for north (note: there are 8 possible directions in total).

Input

The first line of input consists of three positive numbers, the number of lines, 0 < L <= 1000, the number of columns, 0 < C <= 1000, and the number of words to be found, 0 < W <= 1000. The following L input lines, each one of size C characters, contain the word puzzle. Then at last the W words are input one per line.

Output

Your program should output, for each word (using the same order as the words were input) a triplet defining the coordinates, line and column, where the first letter of the word appears, followed by a letter indicating the orientation of the word according to the rules define above. Each value in the triplet must be separated by one space only.

Sample Input

20 20 10
QWSPILAATIRAGRAMYKEI
AGTRCLQAXLPOIJLFVBUQ
TQTKAZXVMRWALEMAPKCW
LIEACNKAZXKPOTPIZCEO
FGKLSTCBTROPICALBLBC
JEWHJEEWSMLPOEKORORA
LUPQWRNJOAAGJKMUSJAE
KRQEIOLOAOQPRTVILCBZ
QOPUCAJSPPOUTMTSLPSF
LPOUYTRFGMMLKIUISXSW
WAHCPOIYTGAKLMNAHBVA
EIAKHPLBGSMCLOGNGJML
LDTIKENVCSWQAZUAOEAL
HOPLPGEJKMNUTIIORMNC
LOIUFTGSQACAXMOPBEIO
QOASDHOPEPNBUYUYOBXB
IONIAELOJHSWASMOUTRK
HPOIYTJPLNAQWDRIBITG
LPOINUYMRTEMPTMLMNBO
PAFCOPLHAVAIANALBPFS
MARGARITA
ALEMA
BARBECUE
TROPICAL
SUPREMA
LOUISIANA
CHEESEHAM
EUROPA
HAVAIANA
CAMPONESA

Sample Output

0 15 G
2 11 C
7 18 A
4 8 C
16 13 B
4 15 E
10 3 D
5 1 E
19 7 C
11 11 H

题解

忽然不明白为什么要存反建图
正着存串也可以啊，然后找到了结束位置就减去对应的向量就好
对于每一行每一列每一对角线跑AC自动机就好

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #include <queue>
  9. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  10. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  11. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  12. #define MAXN 10005
  13. #define MAXM 100005
  14. #define mod 1000000007
  15. //#define ivorysi
  16. using namespace std;
  17. typedef long long ll;
  18. ll read() {
  19.     ll res=0,neg=1;
  20.     char c=getchar();
  21.     while(c<'0' || c>'9') {
  22.     if(c=='-') neg=-1;
  23.     c=getchar();
  24.     }
  25.     while(c>='0' && c<='9') {
  26.     res=res*10+c-'0';
  27.     c=getchar();
  28.     }
  29.     return res*neg;
  30. }
  31. struct node {
  32.     int next[26];
  33.     int danger,prev;
  34. }tr[1000005];
  35. int l,c,w,cnt=1,fa[1005];
  36. int ansx[1005],ansy[1005],d[1005],len[1005];
  37. char *dir="ABCDEFGH",str[1005],puzzle[1005][1005];;
  38. int dx[]={-1,-1,0,1,1,1,0,-1};
  39. int dy[]={0,1,1,1,0,-1,-1,-1};
  40. int getfa(int x) {
  41.     return fa[x]==x ? x:fa[x]=getfa(fa[x]);
  42. }
  43. void ins(int x) {
  44.     int p=1;
  45.     siji(i,1,len[x]) {
  46.     if(tr[p].next[str[i]-'A']==0) {
  47.         tr[p].next[str[i]-'A']=++cnt;
  48.     }
  49.     p=tr[p].next[str[i]-'A'];
  50.     }
  51.     if(tr[p].danger) {
  52.     fa[getfa(x)]=getfa(tr[p].danger);
  53.     }
  54.     else {
  55.     tr[p].danger=x;
  56.     }
  57. }
  59. queue<int> que;
  60. void buildfail() {
  61.     tr[1].prev=1;
  62.     siji(i,0,25) {
  63.     if(tr[1].next[i]==0) {
  64.         tr[1].next[i]=1;
  65.     }
  66.     else {
  67.         tr[tr[1].next[i]].prev=1;
  68.         que.push(tr[1].next[i]);
  69.     }
  70.     }
  71.     while(!que.empty()) {
  72.     int now=que.front();que.pop();
  73.     siji(i,0,25) {
  74.         int z=tr[now].next[i],l=tr[now].prev;
  75.         l=tr[l].next[i];
  76.         if(z!=0) {
  77.         que.push(z);
  78.         tr[z].prev=l;
  79.         }
  80.         else {
  81.         tr[now].next[i]=l;
  82.         }
  83.     }
  84.     if(tr[now].danger==0 && tr[tr[now].prev].danger) {
  85.         tr[now].danger=tr[tr[now].prev].danger;
  86.     }
  87.     }
  88. }
  89. void solve(int a,int b,int t) {
  90.     int p=1;
  91.     while(1) {
  92.     if(a<=0 || a>l) break;
  93.     if(b<=0 || b>c) break;
  94.     p=tr[p].next[puzzle[a][b]-'A'];
  95.     int ap=p;
  96.     while(tr[ap].danger) {
  97.         int k=tr[ap].danger;
  98.         ansx[k]=a-dx[t]*(len[k]-1);
  99.         ansy[k]=b-dy[t]*(len[k]-1);
  100.         d[k]=t;
  101.         ap=tr[ap].prev;
  102.     }
  103.     a+=dx[t];
  104.     b+=dy[t];
  105.     }
  106. }
  107. void solve() {
  108.     l=read();c=read();w=read();
  109.     siji(i,1,l) {
  110.     scanf("%s",puzzle[i]+1);
  111.     }
  112.     siji(i,1,w) {
  113.     fa[i]=i;
  114.     scanf("%s",str+1);
  115.     len[i]=strlen(str+1);
  116.     ins(i);
  117.     }
  118.     buildfail();
  119.     siji(t,0,7) {
  120.     siji(j,1,c) {
  121.         solve(1,j,t);
  122.         solve(l,j,t);
  124.     }
  125.     siji(i,1,l) {
  126.         solve(i,1,t);
  127.         solve(i,c,t);
  128.     }
  129.     }
  130.     siji(i,1,w) {
  131.     printf("%d %d %c\n",ansx[i]-1,ansy[i]-1,dir[d[i]]);
  132.     }
  133. }
  134. int main() {
  135. #ifdef ivorysi
  136.     freopen("f1.in","r",stdin);
  137. #endif
  138.     solve();
  139. }

POJ 4052 Problem I. Hrinity

Description

In the Christian religion, the Trinity is the union of the Father, the Son, and the
Holy Spirit in one God.Recently in a far-far-away country, a new word "Hrinity" was created and bec a me very popular. "Hrinity" means "The son is the father, and the father is the son." But the word "Hrinity" has nothing to do with God or any religion. It's about a writer and his son. When the son wasin highschool, he failed all exams of all courses. As a none famous writer, the son's worrying father carried out a bold plan: he wrote a long novel and declared that it's his 16 year old son's work. An idiot kid can write a long novel? That made a press interested and the press published the novel. Since then, the son got famous and rich, and his father has been keep writing novels and articles on his son's name.But the father doesn
't trust his son because his son is a punk.
Afraid of being treated badly by his son when becomingold, the father embedded "text finger prints" in all the novels and articles. If the son treats him badly, the father will stand out and declare that his son is a fake writer. The father can point out the "text finger prints" in those works to prove that he actually is the author. A text finger print is a delicate sentence which if you add、delete or change the
punctuations in it, it's meaning will become totally different. In all his works, the father write many text finger prints whose meaning can be changed into something like
"my father wrote this article"、"I am a fake writer", etc.
In case of forgetting where the finger prints are, the father needs a computer program to find
out how many finger prints are there in a given article. He offers $20,000,000 to buy the program. Do you want this money?To simplify the problem, we assume that the articles are all written in capital English letters and without blanks.

Input

There are multiple test
cases. The first line in the input is an integer T ( T<= 15)
indicating the number of test cases.
For each test case:The first line is a integer n( 0 < n <= 2500) indicating the number of
text finger prints.
Then n lines follows, each represents a text finger print. It’s guaranteed that these n strings are all different. A finger print at least consists of one letter.The last line of a test case is thearticle. The text finger prints and the article may be described in a compressed format. A compressed string consists of capital letters and “compressors”. A “compressor” is in the following format:
[qx]
q is a number( 0 < q <= 5,000,000)and x is a capital letter. It means q consecutive letter xs in the original uncompressed string. For example, [6K] means ‘KKKKKK’ in the original string. So, if a compressed string is like:
AB[2D]E[7K]G
It actually is ABDDEKKKKKKKG after decompressed to original format.
The length of the article is at least 1 and at most 5,100,000, no matter in the compressed format or a
fter it is decompressed to original format.The length of a text finger printb is no more than 1,100, no matter compressed or original.

Output

For each test case, print an integer K in a line meaning that the article includes K text finger prints.
PLEASE NOTE: If finger print s1 is a sub string of finger print s2 and s2 is included in the article,then s1 doesn't count(s1 can be regarded as doesn't exists).
Multiple appearances of a finger print in the article are just counted as one.

Sample Input

4
2
AB
DCB
DACB
3
A
AB
ABC
DABC
2
[2A]
[3A]B
[5A]B
[4A]B
3
AB
CD
EF
ABCDEF

Sample Output

0
1
1
3

题解

这道题的格式调的我累死了
一开始我还以为模式串总长度是5100000，每次清一遍0就1s了啊！！！！然后我很愉快的TLE了
还很sb的改改改
这道题先建一个AC自动机
然后给每个点打上访问标记，之后对于每个访问过的节点把它到父亲的路上和后缀节点都标记为不合法
但是！这道题有问题
它不传prev节点的结束标记，对于这样一个数据，它的答案和题面不符
1
2
ABCD
BC
ABC
会输出0而不会输出1
这道题不是很好

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #include <queue>
  9. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  10. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  11. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  12. #define MAXN 5100005
  13. #define MAXM 100005
  14. #define mod 1000000007
  15. //#define ivorysi
  16. using namespace std;
  17. typedef long long ll;
  18. ll read() {
  19.     ll res=0,neg=1;
  20.     char c=getchar();
  21.     while(c<'0' || c>'9') {
  22.     if(c=='-') neg=-1;
  23.     c=getchar();
  24.     }
  25.     while(c>='0' && c<='9') {
  26.     res=res*10+c-'0';
  27.     c=getchar();
  28.     }
  29.     return res*neg;
  30. }
  31. struct node {
  32.     int next[26];
  33.     int prev,fa;
  34. }tr[200005];
  35. int nodecnt=1,n,T;
  36. bool ed[200005],vis[200005],lab[200005];
  37. char s[MAXN];
  38. void ins(int x) {
  39.     int len=strlen(s+1),p=1;
  40.     siji(i,1,len) {
  41.         int cnt=0;
  42.         bool flag=0;
  43.         if(s[i]=='[') {
  44.             flag=1;
  45.             ++i;
  46.             while(s[i]>='0' && s[i]<='9') {
  47.                 cnt=cnt*10+s[i]-'0';
  48.                 ++i;
  49.             }
  50.         }
  51.         else cnt=1;
  52.         siji(j,1,cnt) {
  53.             if(tr[p].next[s[i]-'A']==0) {
  54.                 tr[p].next[s[i]-'A']=++nodecnt;
  55.                 tr[nodecnt].fa=p;
  56.             }
  57.             p=tr[p].next[s[i]-'A'];
  58.         }
  59.         if(flag) {
  60.             ++i;
  61.         }
  62.     }
  63.     ed[p]=1;
  64. }
  65. queue<int> que;
  66. void buildfail() {
  67.     tr[1].prev=1;
  68.     siji(i,0,25) {
  69.         if(tr[1].next[i]==0) {
  70.             tr[1].next[i]=1;
  71.         }
  72.         else {
  73.             tr[tr[1].next[i]].prev=1;
  74.             que.push(tr[1].next[i]);
  75.         }
  76.     }
  77.     while(!que.empty()) {
  78.         int now=que.front();que.pop();
  79.         siji(i,0,25) {
  80.             int v=tr[now].next[i],l=tr[now].prev;
  81.             if(v==0) {
  82.                 tr[now].next[i]=tr[l].next[i];
  83.             }
  84.             else {
  85.                 tr[v].prev=tr[l].next[i];
  86.                 que.push(v);
  87.             }
  88.         }
  89.         //if(ed[tr[now].prev]) ed[now]=1;
  90.     }
  91. }
  92. void process() {
  93.     int len=strlen(s+1),p=1;
  94.     siji(i,1,len) {
  95.         int cnt=0;
  96.         bool flag=0;
  97.         if(s[i]=='[') {
  98.             ++i;
  99.             flag=1;
  100.             while(s[i]>='0' && s[i]<='9') {
  101.                 cnt=cnt*10+s[i]-'0';
  102.                 ++i;
  103.             }
  104.         }
  105.         else cnt=1;
  106.         siji(j,1,cnt) {
  107.             p=tr[p].next[s[i]-'A'];
  108.             if(ed[p]) vis[p]=1;
  109.         }
  110.         if(flag) ++i;
  111.     }
  113. }
  114. void dfs(int u) {
  115.     if(lab[u] || u==1 || u==0) return;
  116.     lab[u]=1;
  117.     vis[u]=0;
  118.     dfs(tr[u].fa);
  119.     dfs(tr[u].prev);
  120. }
  121. void solve() {
  122.     nodecnt=1;
  123.     memset(tr,0,sizeof(tr));
  124.     memset(ed,0,sizeof(ed));
  125.     memset(vis,0,sizeof(vis));
  126.     memset(lab,0,sizeof(lab));
  128.     n=read();
  129.     siji(i,1,n) {
  130.     scanf("%s",s+1);
  131.         ins(i);
  132.     }
  133.     buildfail();
  134.     scanf("%s",s+1);
  135.     process();
  136.     int ans=0;
  138.     siji(i,1,nodecnt) {
  139.         if((!lab[i]) && vis[i]) {
  140.             dfs(tr[i].fa);
  141.             dfs(tr[i].prev);
  142.         }
  143.     }
  144.     siji(i,1,nodecnt) {
  145.         if(vis[i]) ++ans;
  146.     }
  147.     printf("%d\n",ans);
  148. }
  149. int main() {
  150. #ifdef ivorysi
  151.     freopen("f1.in","r",stdin);
  152. #endif
  153.     T=read();
  154.     while(T--) {
  155.         solve();
  156.     }
  157. }

HDU 3065 病毒侵袭持续中

Problem Description

小t非常感谢大家帮忙解决了他的上一个问题。然而病毒侵袭持续中。在小t的不懈努力下，他发现了网路中的“万恶之源”。这是一个庞大的病毒网站，他有着好多好多的病毒，但是这个网站包含的病毒很奇怪，这些病毒的特征码很短，而且只包含“英文大写字符”。当然小t好想好想为民除害，但是小t从来不打没有准备的战争。知己知彼，百战不殆，小t首先要做的是知道这个病毒网站特征：包含多少不同的病毒，每种病毒出现了多少次。大家能再帮帮他吗？

Input

第一行，一个整数N（1<=N<=1000），表示病毒特征码的个数。
接下来N行，每行表示一个病毒特征码，特征码字符串长度在1—50之间，并且只包含“英文大写字符”。任意两个病毒特征码，不会完全相同。
在这之后一行，表示“万恶之源”网站源码，源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符（不包括回车）。

Output

按以下格式每行一个，输出每个病毒出现次数。未出现的病毒不需要输出。
病毒特征码: 出现次数
冒号后有一个空格，按病毒特征码的输入顺序进行输出。

Sample Input

3
AA
BB
CC
ooxxCC%dAAAoen....END

Sample Output

AA: 2
CC: 1

Hint

Hit：
题目描述中没有被提及的所有情况都应该进行考虑。比如两个病毒特征码可能有相互包含或者有重叠的特征码段。
计数策略也可一定程度上从Sample中推测。

题解

垃圾题面，多组数据还不告诉，垃圾题面！！！
这道题我们记录每个点被访问了多少次，按照bfs序的倒序向上累加到prev结点上就可以了（最近的prev就可以，道理和kmp差不多）

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #include <queue>
  9. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  10. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  11. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  12. #define MAXN 50005
  13. #define MAXM 100005
  14. #define mod 1000000007
  15. //#define ivorysi
  16. using namespace std;
  17. typedef long long ll;
  18. ll read() {
  19.     ll res=0,neg=1;
  20.     char c=getchar();
  21.     while(c<'0' || c>'9') {
  22.     if(c=='-') neg=-1;
  23.     c=getchar();
  24.     }
  25.     while(c>='0' && c<='9') {
  26.     res=res*10+c-'0';
  27.     c=getchar();
  28.     }
  29.     return res*neg;
  30. }
  31. struct node {
  32.     int next[26];
  33.     int prev;
  34. }tr[MAXN];
  35. int nodecnt=1,n;
  36. int pos[MAXN],vis[MAXN],line[MAXN],tot,ans[1005];
  37. char s[2000005],str[1005][55];
  38. void ins(int x) {
  39.     int p=1;
  40.     int len=strlen(str[x]+1);
  41.     siji(i,1,len) {
  42.     if(tr[p].next[str[x][i]-'A']==0) {
  43.         tr[p].next[str[x][i]-'A']=++nodecnt;
  44.     }
  45.     p=tr[p].next[str[x][i]-'A'];
  46.     }
  47.     pos[p]=x;
  48. }
  49. queue<int> que;
  50. void buildfail() {
  51.     tr[1].prev=1;
  52.     siji(i,0,25) {
  53.     if(tr[1].next[i]==0) {
  54.         tr[1].next[i]=1;
  55.     }
  56.     else {
  57.         int k=tr[1].next[i];
  58.         tr[k].prev=1;
  59.         que.push(k);
  60.     }
  61.     }
  62.     while(!que.empty()) {
  63.     int now=que.front();que.pop();
  64.     line[++tot]=now;
  65.     siji(i,0,25) {
  66.         int l=tr[now].prev,z=tr[now].next[i];
  67.         if(z==0) {
  68.         tr[now].next[i]=tr[l].next[i];
  69.         }
  70.         else {
  71.         tr[z].prev=tr[l].next[i];
  72.         que.push(z);
  73.         }
  74.     }
  75.     }
  76. }
  77. bool solve() {
  78.     if(scanf("%d",&n)==EOF) return false;
  79.     memset(tr,0,sizeof(tr));
  80.     nodecnt=1;
  81.     memset(pos,0,sizeof(pos));
  82.     memset(vis,0,sizeof(vis));
  83.     memset(line,0,sizeof(line));
  84.     tot=0;
  85.     memset(ans,0,sizeof(ans));
  86.     siji(i,1,n) {
  87.     scanf("%s",str[i]+1);
  88.     ins(i);
  89.     }
  90.     buildfail();
  91.     scanf("%s",s+1);
  92.     int len=strlen(s+1);
  93.     int p=1;
  94.     siji(i,1,len) {
  95.     if(s[i]<'A' || s[i]>'Z') p=1;
  96.     else {
  97.         p=tr[p].next[s[i]-'A'];
  98.     }
  99.     ++vis[p];
  100.     }
  101.     gongzi(i,tot,1) {
  102.     int k=line[i];
  103.     vis[tr[k].prev]+=vis[k];
  104.     }
  105.     siji(i,1,nodecnt) {
  106.     ans[pos[i]]=vis[i];
  107.     }
  108.     siji(i,1,n) {
  109.     if(ans[i]>0) {
  110.         printf("%s: %d\n",str[i]+1,ans[i]);
  111.     }
  112.     }
  113.     return true;
  114. }
  115. int main() {
  116. #ifdef ivorysi
  117.     freopen("f1.in","r",stdin);
  118. #endif
  119.     while(1) {
  120.     if(!solve()) break;
  121.     }
  122. }

manacher

BZOJ 2565: 最长双回文串

Description

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。
输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。

Input

一行由小写英文字母组成的字符串S。

Output

一行一个整数，表示最长双回文子串的长度。

Sample Input

baacaabbacabb

Sample Output

12

HINT

样例说明

从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分，且两者都是回文串。
对于100%的数据，2≤|S|≤10^5
2015.4.25新加数据一组

题解

先跑马拉车，然后dp
f[i]表示从i往前能有多长的回文串,g[i]表示从i往后能有多少的回文串
更新的时候单调队列优化

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #include <queue>
  9. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  10. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  11. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  12. #define MAXN 100005
  13. #define mod 1000000007
  14. //#define ivorysi
  15. using namespace std;
  16. typedef long long ll;
  17. ll read() {
  18.     ll res=0,neg=1;
  19.     char c=getchar();
  20.     while(c<'0' || c>'9') {
  21.     if(c=='-') neg=-1;
  22.     c=getchar();
  23.     }
  24.     while(c>='0' && c<='9') {
  25.     res=res*10+c-'0';
  26.     c=getchar();
  27.     }
  28.     return res*neg;
  29. }
  30. char s[MAXN],str[MAXN*2];
  31. int f[MAXN],g[MAXN],len,r[MAXN*2];
  32. int q[MAXN*2],h,t;
  33. bool solve() {
  34.     scanf("%s",s+1);
  35.     len=strlen(s+1);
  36.     siji(i,1,len) {
  37.     str[i*2-1]='$';
  38. 	str[i*2]=s[i];
  39.     }
  40.     str[len*2+1]='$';
  41.     int pos=0,maxright=0;
  42.     siji(i,1,len*2+1) {
  43.     if(maxright > i) r[i]=min(r[2*pos-i],maxright-i+1);
  44.     r[i]=max(r[i],1);
  45.     while(i-r[i]>=1 && i+r[i]<=len*2+1 && str[i-r[i]]==str[i+r[i]]) ++r[i];
  46.     if(i+r[i]-1>maxright) {
  47.         maxright=i+r[i]-1;
  48.         pos=i;
  49.     }
  50.     }
  51.     h=1,t=0;
  52.     siji(i,1,len) {
  53.     while(h<=t) {//这里是h<=t 不合法就全部清空了
  54.         if(q[h]+r[q[h]]-1 < i*2) ++h;
  55.         else break;
  56.     }
  57.     if(h<=t) {
  58.         f[i]=(i*2-q[h])+1;
  59.     }
  60.     else f[i]=1;
  61.     if(h>t || q[t]+r[q[t]]-1 < i*2-1+r[i*2-1]-1) {
  62.         q[++t]=i*2-1;
  63.     }
  64.     if(h>t || q[t]+r[q[t]]-1 < i*2+r[i*2]-1) {
  65.         q[++t]=i*2;
  66.     }
  67.     }
  68.     h=1,t=0;
  69.     gongzi(i,len,1) {
  70.     while(h<=t) {
  71.         if(q[h]-r[q[h]]+1 > i*2) ++h;
  72.         else break;
  73.     }
  74.     if(h<=t) {
  75.         g[i]=(q[h]-i*2)+1;
  76.     }
  77.     else g[i]=1;
  78.     if(h>t || q[t]-r[q[t]]+1 > i*2-1-r[i*2-1]+1) {
  79.         q[++t]=i*2-1;
  80.     }
  81.     if(h>t || q[t]-r[q[t]]+1 > i*2-r[i*2]+1) {
  82.         q[++t]=i*2;
  83.     }
  84.     }
  85.     int ans=0;
  86.     xiaosiji(i,1,len) {
  87.     ans=max(f[i]+g[i+1],ans);
  88.     }
  89.     printf("%d\n",ans);
  90. }
  91. int main() {
  92. #ifdef ivorysi
  93.     freopen("f1.in","r",stdin);
  94. #endif
  95.     solve();
  96. }

codeforce 17 E. Palisection

In an English class Nick had nothing to do at all, and remembered about wonderful strings called palindromes. We should remind you that a string is called a palindrome if it can be read the same way both from left to right and from right to left. Here are examples of such strings: «eye», «pop», «level», «aba», «deed», «racecar», «rotor», «madam».
Nick started to look carefully for all palindromes in the text that they were reading in the class. For each occurrence of each palindrome in the text he wrote a pair — the position of the beginning and the position of the ending of this occurrence in the text. Nick called each occurrence of each palindrome he found in the text subpalindrome. When he found all the subpalindromes, he decided to find out how many different pairs among these subpalindromes cross. Two subpalindromes cross if they cover common positions in the text. No palindrome can cross itself.
Let's look at the actions, performed by Nick, by the example of text «babb». At first he wrote out all subpalindromes:
• «b» — 1..1
• «bab» — 1..3
• «a» — 2..2
• «b» — 3..3
• «bb» — 3..4
• «b» — 4..4
Then Nick counted the amount of different pairs among these subpalindromes that cross. These pairs were six:
1. 1..1 cross with 1..3
2. 1..3 cross with 2..2
3. 1..3 cross with 3..3
4. 1..3 cross with 3..4
5. 3..3 cross with 3..4
6. 3..4 cross with 4..4
Since it's very exhausting to perform all the described actions manually, Nick asked you to help him and write a program that can find out the amount of different subpalindrome pairs that cross. Two subpalindrome pairs are regarded as different if one of the pairs contains a subpalindrome that the other does not.

Input

The first input line contains integer n (1 ≤ n ≤ 2·106) — length of the text. The following line contains n lower-case Latin letters (from a to z).

Output

In the only line output the amount of different pairs of two subpalindromes that cross each other. Output the answer modulo 51123987.

Examples

Input

4
babb

Output

6

Input

2
aa

Output

2

题解

这道题用到了正难则反的思想
我们先求出一共有多少个回文串他们两两搭配
然后去除掉没有相交部分的字符串
f[i]表示以i为结尾的回文串有多少个
g[i]表示以i为开头的回文串有多少个
这可以用查分统计……
然后将g处理成后缀和
要注意不断的取模……因为数据会很大

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #include <queue>
  9. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  10. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  11. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  12. #define MAXN 4000005
  13. #define mod 51123987
  14. //#define ivorysi
  15. using namespace std;
  16. typedef long long ll;
  17. ll read() {
  18.     ll res=0,neg=1;
  19.     char c=getchar();
  20.     while(c<'0' || c>'9') {
  21.     if(c=='-') neg=-1;
  22.     c=getchar();
  23.     }
  24.     while(c>='0' && c<='9') {
  25.     res=res*10+c-'0';
  26.     c=getchar();
  27.     }
  28.     return res*neg;
  29. }
  30. char s[MAXN],str[MAXN*2];
  31. int len,r[MAXN*2],n;
  32. int f[MAXN],g[MAXN];
  33. ll ans;
  34. void solve() {
  35.     scanf("%d %s",&n,s+1);
  36.     if(n==1) {
  37.     puts("0");return;
  38.     }
  39.     siji(i,1,n) {
  40.     str[i*2-1]='$';
  41. 	str[i*2]=s[i];
  42.     }
  43.     str[n*2+1]='$';
  44.     int pos=0,maxright=0;
  45.     siji(i,1,n*2+1) {
  46.     if(maxright >= i) r[i]=min(r[2*pos-i],maxright-i+1);
  47.     r[i]=max(r[i],1);
  48.     while(i-r[i]>=1 && i+r[i]<=n*2+1 && str[i-r[i]]==str[i+r[i]]) {
  49.         ++r[i];    
  50.     }
  51.     if(i+r[i]-1>maxright) {
  52.         maxright=i+r[i]-1;
  53.         pos=i;
  54.     }
  55.     }
  56.     siji(i,1,n*2+1) {
  57.     if(i%2==0) {
  58.         f[i/2]++;
  59.         f[(i+r[i]-1)/2+1]--;
  60.         g[i/2+1]--;
  61.         g[(i-r[i]+1)/2+1]++;
  62.         ans+=(r[i]-1)/2+1;
  63.         ans%=mod;
  64.     }
  65.     else {
  66.         f[i/2+1]++;
  67.         f[(i+r[i]-1)/2+1]--;
  68.         g[i/2+1]--;
  69.         g[(i-r[i]+1)/2+1]++;
  70.         ans+=(r[i]-1)/2;
  71.         ans%=mod;
  72.     }
  73.     }
  74.     ans=ans*(ans-1)/2;
  75.     ans%=mod;
  76.     f[0]=0;f[n+1]=0;
  77.     g[0]=0;g[n+1]=0;
  78.     siji(i,1,n) {
  79.     f[i]+=f[i-1];
  80.     f[i]%=mod;
  81.     g[i]+=g[i-1];
  82.     g[i]%=mod;
  83.     }
  85.     gongzi(i,n,1) {
  86.     g[i]+=g[i+1];
  87.     g[i]%=mod;
  88.     }
  89.     siji(i,1,n-1) {
  90.     ans-=(ll)f[i]*g[i+1]%mod;
  91.     ans=(ans%mod+mod)%mod;
  92.     }
  93.     printf("%lld\n",ans);
  94. }
  95. int main() {
  96. #ifdef ivorysi
  97.     freopen("f1.in","r",stdin);
  98. #endif
  99.     solve();
  100.     return 0;
  102. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注