fork(3) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Transform S into T.
  5. // For example, S = "abba", T = "^#a#b#b#a#$".
  6. // ^ and $ signs are sentinels appended to each end to avoid bounds checking
  7. string preProcess(string s) 
  8. {
  9.   int n = s.length();
  10.   if (n == 0) return "^$";
  11.   string ret = "^";
  12.   for (int i = 0; i < n; i++)
  13.     ret += "#" + s.substr(i, 1);
  14.  
  15.   ret += "#$";
  16.   return ret;
  17. }
  18.  
  19. //Manacher's Algorithm to find longest palindromic substring in O(n)
  20. int dp[299999]={0};
  21. int idx;
  22.  
  23. string Manachers(string s) 
  24. {
  25.   string T = preProcess(s);
  26.   int n = T.length();
  27.   int *P = new int[n];
  28.   int C = 0, R = 0;
  29.   for (int i = 1; i < n-1; i++) 
  30.   {
  31.     int i_mirror = 2*C-i; // equals to i' = C - (i-C)
  32.  
  33.     P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;
  34.  
  35.     // Attempt to expand palindrome centered at i
  36.     while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
  37.       P[i]++;
  38.  
  39.     // If palindrome centered at i expand past R,
  40.     // adjust center based on expanded palindrome.
  41.     if (i + P[i] > R) 
  42.     {
  43.       C = i;
  44.       R = i + P[i];
  45.     }
  46.   }
  47.  
  48.   // Find the maximum element in P.
  49.   int maxLen = 0;
  50.   idx=0;
  51.   int centerIndex = 0;
  52.   for (int i = 1; i < n-1; i++) 
  53.   {
  54.   	if(P[i]>0)
  55.   	{
  56.   		dp[idx]=P[i];
  57.   		++idx;
  58.   	}
  59.     if (P[i] > maxLen) 
  60.     {
  61.       maxLen = P[i];
  62.       centerIndex = i;
  63.     }
  64.   }
  65.   delete[] P;
  66.  
  67.   return s.substr((centerIndex - 1 - maxLen)/2, maxLen);
  68. }
  69.  
  70. int primes[199998+15];
  71.  
  72. void initialise()
  73. {
  74. 	int i;
  75. 	for(i=0;i<199998;i++)
  76. 	{
  77. 		primes[i]=0;
  78. 	}
  79. }
  80.  
  81. void sieve()
  82. {
  83. 	int i,j;
  84. 	primes[0]=1;
  85. 	primes[1]=1;
  86. 	for(i=2;i<=199997;i++)
  87. 	{
  88. 		if(!primes[i])
  89. 		{
  90. 			for(j=2*i;j<=199997;j+=i)
  91. 			primes[j]=1;
  92. 		}
  93. 	}
  94. }
  95. int main() 
  96. {
  97. 	initialise();
  98. 	sieve();
  99. 	int T;
  100. 	string str;
  101. 	/*for(int i=0;i<idx;i++)
  102. 	cout<<dp[i]<<" ";*/
  103. 	scanf("%d",&T);
  104. 	while(T--)
  105. 	{
  106. 		cin>>str;
  107. 		Manachers(str);
  108. 		int cnt=0;
  109. 		for(int i=0;i<idx;i++)
  110. 		{
  111. 			if(!primes[dp[i]])
  112. 			++cnt;
  113. 		}
  114. 		printf("%d\n",cnt);
  115. 		/*for(int i=0;i<idx;i++)
  116. 		cout<<dp[i]<<" ";*/
  117.  
  118. 		//printf("\n");
  119. 	}
  120. 	return 0;
  121. }
Success #stdin #stdout 0s 5388KB
comments (?)
stdin
copy 
2
ababac
abac
stdout
copy 
3
1
https://ideone.com/svJ7ot
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!