fork(1) download
copy 
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. #include<string.h>
  5. using namespace std;
  6. int max(int a,int b)
  7. {
  8. 	return a>b?a:b;
  9. }
  10. int max(int a,int b,int c)
  11. {
  12. 	return max(max(a,b),c);
  13. }
  14. int search(vector<char> v,char c)
  15. {
  16. 	vector<char>::iterator it;
  17. 	for(it=v.begin();it<v.end();it++)
  18. 	{
  19. 		if(c==(*it))
  20. 		   return 1;
  21. 	}
  22. 	return 0;
  23. }
  24. int crossing_mid(char str[],int low,int mid,int high)
  25. {
  26. 	vector<char> v;
  27. 	v.push_back(str[mid]);
  28. 	int i=mid-1;int j=mid+1;
  29. 	while(str[i]!=str[j])
  30. 	{
  31. 		int k=search(v,str[i]);
  32. 		int l=search(v,str[j]);
  33. 		if((!k)&&(!l))
  34. 		{
  35. 			v.push_back(str[i]);
  36. 			v.push_back(str[j]);
  37. 			i--;j++;
  38. 		}
  39. 		if(k)
  40. 		{
  41. 			while((j<=high)&&(!search(v,str[j])))
  42. 			{
  43. 				v.push_back(str[j]);
  44. 				j++;
  45. 			}
  46. 			return v.size();
  47. 		}
  48. 		if(l)
  49. 		{
  50. 			while((i>=low)&&(!search(v,str[i])))
  51. 			{
  52. 				v.push_back(str[i]);
  53. 				i--;
  54. 			}
  55. 			return v.size();
  56. 		}
  57. 	}
  58. 	int s=v.size();
  59. 	while((j<=high)&&(!search(v,str[j])))
  60. 	{
  61. 		v.push_back(str[j]);
  62. 		j++;
  63. 	}
  64. 	int p=v.size();
  65. 	v.resize(s);
  66. 	while((i>=low)&&(!search(v,str[i])))
  67. 	{
  68. 		v.push_back(str[i]);
  69. 		i--;
  70. 	}
  71. 	int q=v.size();
  72. 	return max(p,q);
  73.  
  74. }
  75. int fun(char str[],int low,int high)
  76. {
  77. 	if(low==high)
  78. 	    return 1;
  79. 	if(high-low==1)
  80. 	    return str[low]==str[high]?1:2;
  81. 	int mid=(low+high)/2;
  82. 	return max(fun(str,low,mid-1),
  83. 	           fun(str,mid+1,high),
  84. 			   crossing_mid(str,low,mid,high));
  85. }
  86. int main()
  87. {
  88. 	char str[]="geeksforgeeks";
  89. 	cout<<fun(str,0,strlen(str)-1)<<" is the max non repeatong substring.\n";
  90. 	return 0;
  91. }
Success #stdin #stdout 0s 3432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
7 is the max non repeatong substring.
https://ideone.com/eDWtc8
language:
C++ (gcc 8.3)
created:
10 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!