fork(7) download
  1. #include <cstdio>
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6. const int maxn=100060;
  7. const int sigma=26;
  8. int n=0;
  9. char s[maxn];
  10.  
  11. struct palindrome_tree
  12. {
  13. struct state
  14. {
  15. int len,link;
  16. int to[sigma];
  17. state():len(-1),link(-1){}
  18. } st[maxn];
  19. int last,sz;
  20. palindrome_tree():last(1),sz(2){st[1].len=st[1].link=0;}
  21.  
  22. int add_letter()
  23. {
  24. char c=s[n-1];
  25. int p=last;
  26. while(p!=-1 && c!=s[n-st[p].len-2]) p=st[p].link;
  27. if(p==-1)
  28. {
  29. last=1;
  30. return 0;
  31. }
  32. int ret=0;
  33. if(!st[p].to[c])
  34. {
  35. ret=1;
  36. int q=last=sz++;
  37. st[p].to[c]=q;
  38. st[q].len=st[p].len+2;
  39. do p=st[p].link; while(p!=-1 && c!=s[n-st[p].len-2]);
  40. if(p==-1) st[q].link=1;
  41. else st[q].link=st[p].to[c];
  42. }
  43. else last=st[p].to[c];
  44. return ret;
  45. }
  46. };
  47.  
  48.  
  49. int main()
  50. {
  51. palindrome_tree me;
  52. ios::sync_with_stdio(0);
  53. s[n++]='#';
  54. int cur=0;
  55. while((s[n++]=getchar())!='\n')
  56. {
  57. s[n-1]-='a';
  58. cout<<(cur+=me.add_letter())<<' ';
  59. }
  60. }
  61.  
Runtime error #stdin #stdout 0s 3388KB
stdin
Standard input is empty
stdout
Standard output is empty