fork download
copy 
  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<string>
  4. using namespace std;
  5. string convert(string s,int n) 
  6. {
  7. 	string ret = "^";
  8. 	for (int i = 0; i < n; i++)
  9. 		ret += "#" + s.substr(i, 1);
  10. 	ret += "#$";
  11. 	return ret;
  12. }
  13. void solve(string s) 
  14. {
  15. 	string str = convert(s,s.length());
  16. 	int n = str.length();
  17. 	int pall[n];
  18. 	for(int i=0;i<n;i++)
  19. 		pall[i]=0;
  20. 	int center = 0, right = 0;
  21. 	for (int i = 1; i < n-1; i++) 
  22. 	{
  23. 		int i_mirror = 2*center-i;
  24. 		pall[i] = (right > i) ? min(right-i, pall[i_mirror]) : 0;
  25. 		while (str[i + 1 + pall[i]] == str[i - 1 - pall[i]])
  26. 			pall[i]++;
  27. 		if (i + pall[i] > right) 
  28. 		{
  29. 			center = i;
  30. 			right = i + pall[i];
  31. 		}
  32. 	}
  33. 	int ans=0;
  34. 	for(int i=0;i<n;i++)
  35. 	{
  36. 		ans+=((pall[i]+1)/2);
  37. 		cout<<pall[i]<<"  ";
  38. 	}
  39. 	printf("%d\n",ans);
  40. }
  41. int main()
  42. {
  43. 	int test;
  44. 	string ip;
  45. 	scanf("%d",&test);
  46. 	while(test--)
  47. 	{
  48. 		cin>>ip;
  49. 		solve(ip);
  50. 	}
  51. 	return 0;
  52. }
Success #stdin #stdout 0s 3280KB
comments (?)
stdin
copy 
2
a
aba
stdout
copy 
0  0  1  0  0  1
0  0  1  0  3  0  1  0  0  4
https://ideone.com/nSw8ZA
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

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!