fork(12) download
copy 
  1. #include <cassert>
  2. #include <cctype>
  3. #include <climits>
  4. #include <cmath>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <cstring>
  8. #include <iostream>
  9. #include <fstream>
  10. #include <sstream>
  11. #include <iomanip>
  12. #include <string>
  13. #include <vector>
  14. #include <deque>
  15. #include <list>
  16. #include <set>
  17. #include <map>
  18. #include <bitset>
  19. #include <stack>
  20. #include <queue>
  21. #include <algorithm>
  22. #include <functional>
  23. #include <iterator>
  24. #include <numeric>
  25. #include <utility>
  26. using namespace std;
  27.  
  28. #define forn(i, n) for(int i = 0; i < (int)(n); i++)
  29. #define ford(i, n) for(int i = (int)(n) - 1; i >= 0; i--)
  30. #define fore(i, a, n) for(int i = (int)(a); i < (int)(n); i++)
  31. #define DEBUG if(0)
  32. #define PAUSE system("pause")
  33. #define READ(f) freopen(f, "r", stdin)
  34. #define WRITE(f) freopen(f, "w", stdout)
  35. #define ALL(c) c.begin(), c.end()
  36. #define PB(x) push_back(x)
  37. #define UB(s, e, x) upper_bound(s, e, x)
  38. #define LB(s, e, x) lower_bound(s, e, x)
  39. #define REV(s, e) reverse(s, e);
  40. #define SZ(c) c.size()
  41. #define SET(p) memset(p, -1, sizeof(p))
  42. #define CLR(p) memset(p, 0, sizeof(p))
  43. #define MEM(p, v) memset(p, v, sizeof(p))
  44. #define LAST(a) (int(a.size()) - 1)
  45. #define PN(n)   printf("%d",n)
  46. #define PDN(n)  printf("%lf",n)
  47. #define PLN(n)  printf("%lld",n)
  48. #define PS(n)   printf("%s",n)
  49. #define PL()    printf("\n")
  50. #define SN(n)   scanf("%d",&n)
  51. #define SDN(n)  scanf("%lf",&n)
  52. #define SLN(n)  scanf("%lld",&n)
  53. #define SS(n)   scanf("%s",n)
  54. #define i64 long long
  55. #define ff first
  56. #define ss second
  57.  
  58. template< class T > T sq(T &x) { return x * x; }
  59. template< class T > T abs(T &n) { return (n < 0 ? -n : n); }
  60. template< class T > T max(T &a, T &b) { return (!(a < b) ? a : b); }
  61. template< class T > T min(T &a, T &b) { return (a < b ? a : b); }
  62. template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
  63. template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
  64. template< class T > T mod(T &a, T &b) { return (a < b ? a : a % b); }
  65. template< class T > bool inside(T &a, T &b, T &c) { return a<=b && b<=c; }
  66. template< class T > void setmax(T &a, T b) { if(a < b) a = b; }
  67. template< class T > void setmin(T &a, T b) { if(b < a) a = b; }
  68.  
  69. const double EPS = 1E-9;
  70. //const int INF = 100000000;
  71. const int INF = 0x3f3f3f3f;
  72. const double PI = 3.1415926535897932384626433832795;
  73. const int MAX = 150;
  74. int dx[]={ 0, 0, -1, 1, -1, 1,-1, 1};
  75. int dy[]={-1, 1,  0, 0, -1,-1, 1, 1};
  76.  
  77.  
  78. string preProcess(string s) {
  79.   int n = s.length();
  80.   if (n == 0) return "^$";
  81.   string ret = "^";
  82.   for (int i = 0; i < n; i++)
  83.     ret += "#" + s.substr(i, 1);
  84.  
  85.   ret += "#$";
  86.   return ret;
  87. }
  88.  
  89. void countPalindrome(int k, string s) {
  90.  
  91.   string T = preProcess(s);
  92.   int n = T.length();
  93.   int *P = new int[n];
  94.   int C = 0, R = 0;
  95.  
  96.   for (int i = 1; i < n-1; i++) {
  97.     int i_mirror = 2*C-i;
  98.  
  99.     P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;
  100.  
  101.  
  102.     while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
  103.       P[i]++;
  104.  
  105.     if (i + P[i] > R) {
  106.       C = i;
  107.       R = i + P[i];
  108.     }
  109.   }
  110.  
  111.  
  112.   set<int>st;
  113.   for (int i = 1; i < n-1; i++) {
  114.     if (P[i] == k ) {
  115.         st.insert((i - 1 - P[i])/2);
  116.     }
  117.   }
  118.   delete[] P;
  119.  
  120.   PN(st.size()); PL();
  121. }
  122.  
  123. int main()
  124. {
  125.     int k;
  126.     SN(k);
  127.     string s;
  128.     cin>>s;
  129.  
  130.     if(k==1) printf("%d\n",s.size());
  131.     else if(k>s.size()) printf("0\n");
  132.     else countPalindrome(k,s);
  133.     return 0;
  134. }
  135.  
Success #stdin #stdout 0s 2992KB
comments (?)
stdin
copy 
5
ababab
stdout
copy 
2
https://ideone.com/kiuE9g
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!