fork download
copy 
  1. /* ****GT_18**** */
  2. //Motivational Source->FUHPD
  3.  
  4. #include<bits/stdc++.h>
  5. #define	MIN(a,b,c)	min(min(a,b),c)
  6. #define	MAX(a,b,c)	max(max(a,b),c)
  7. #define ll          long long
  8. #define itr         vector<ll int>::iterator
  9. #define pb          push_back
  10. #define mp          make_pair
  11. #define pii         pair<ll int,ll int>
  12. #define vi          vector<ll int>
  13. #define all(a)      (a).begin(),(a).end()
  14. #define F           first
  15. #define S           second
  16. #define sz(x)       (ll int)x.size()
  17. #define hell        1000000007
  18. #define endl        '\n'
  19. #define rep(i,a,b)	for(ll int i=a;i<b;i++)
  20. #define lbnd        lower_bound
  21. #define ubnd        upper_bound
  22. #define bs          binary_search
  23. using namespace std;
  24. vi cal_lcs(string k)
  25. {
  26. 	vi f(sz(k)+1);
  27. 	f[0]=0;
  28. 	f[1]=0;
  29. 	rep(i,2,sz(k)+1)
  30. 	{
  31. 		int j=f[i-1];
  32. 		while(1)
  33. 		{
  34. 			if(k[j]==k[i-1])
  35. 			{
  36. 				f[i]=j+1;
  37. 				break;
  38. 			}
  39. 			if(j==0) 
  40. 			{
  41. 				f[i]=0;
  42. 				break;
  43. 			}
  44. 			j=f[j];
  45. 		}
  46. 	}
  47. 	return f;
  48. }
  49. void KMP(string a,string b)
  50. {
  51. 	vi f=cal_lcs(a);
  52. 	int i=0,j=0,fl=0;
  53. 	while(1)
  54. 	{
  55. 		if(j==sz(b))
  56. 		break;
  57.  
  58. 		if(b[j]==a[i])
  59. 		{
  60. 			i++;
  61. 			j++;
  62. 			if(i==sz(a))
  63. 			{
  64. 				fl=1;
  65. 				cout<<j-sz(a)<<endl;
  66. 			}
  67. 		}
  68. 		else if(i) i=f[i];
  69. 		else j++;
  70. 	}
  71. 	if(!fl)cout<<endl;
  72. }
  73. int main()
  74. {
  75. 	ios_base::sync_with_stdio(false);
  76. 	cin.tie(0);
  77. 	cout.tie(0);
  78. 	int TESTS=1;
  79. //	cin>>TESTS;
  80. 	while(cin>>TESTS)
  81. 	{
  82. 		string a,b;
  83. 		cin>>a>>b;
  84. 		KMP(a,b);
  85. 	}
  86. 	return 0;
  87. }
  88.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/m4HdUP
language:
C++14 (gcc 8.3)
created:
7 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!