fork download
copy 
  1. /*
  2. written by- Piyush Golani
  3. language- c++
  4. country- India
  5. College- N.I.T Jamshedpur
  6. */
  7. #include <cmath>
  8. #include <ctime>
  9. #include <iostream>
  10. #include <string>
  11. #include <vector>
  12. #include<cstdio>
  13. #include<sstream>
  14. #include<algorithm>
  15. #include<cstdlib>
  16. #include<cstring>
  17. #include<map>
  18. #include<queue>
  19. #include<cctype>
  20. using namespace std;
  21. #define pb push_back
  22. #define all(s) s.begin(),s.end()
  23. #define f(i,a,b) for(int i=a;i<b;i++)
  24. #define F(i,a,b) for(int i=a;i>=b;i--)
  25. #define PI 3.1415926535897932384626433832795
  26. #define INF 2000000000
  27. #define BIG_INF 7000000000000000000LL
  28. #define mp make_pair
  29. #define eps 1e-9
  30. #define LL long long
  31. #define si(n) scanf("%d",&n)
  32. #define sll(n) scanf("%lld",&n)
  33. #define mod 1000000007
  34. #define mm 10000000
  35.  
  36. string inttostring(int n)
  37. {
  38.     stringstream a;
  39.     a<<n;
  40.     return a.str();
  41. }
  42.  
  43. int stringtoint(string A)
  44. {
  45.     istringstream a(A);
  46.     int p;
  47.     a>>p;
  48.     return p;
  49. }
  50.  
  51. //////////////////////////////////////////////////////
  52.  
  53. char s[200005];
  54. LL substr_count(int n,char *s)
  55. {
  56.     // constructing of suffix array
  57. 	// refer to e-maxx.ru :)
  58. 	vector<int> cnt(128);
  59. 	for(int i=0;i<n;i++)
  60. 		cnt[s[i]]++;
  61. 	for(int i=1;i<128;i++)
  62. 		cnt[i]+=cnt[i-1];
  63. 	vector<int> p(n);
  64. 	for(int i=0;i<n;i++)
  65. 		p[--cnt[s[i]]]=i;
  66. 	vector<vector<int> > c(1,vector<int>(n));
  67. 	int w=0;
  68. 	for(int i=0;i<n;i++)
  69. 	{
  70. 		if(i==0 || s[p[i]]!=s[p[i-1]]) w++;
  71. 		c[0][p[i]] = w-1;
  72. 	}
  73.  
  74. 	for(int k=0,h=1;h<n;k++,h*=2)
  75. 	{
  76. 		vector<int> pn(n);
  77. 		for(int i=0;i<n;i++) {
  78. 			pn[i] = p[i] - h;
  79. 			if(pn[i]<0) pn[i] += n;
  80. 		}
  81. 		vector<int> cnt(w,0);
  82. 		for(int i=0;i<n;i++)
  83. 			cnt[c[k][pn[i]]]++;
  84. 		for(int i=1;i<w;i++)
  85. 			cnt[i]+=cnt[i-1];
  86. 		for(int i=n;i--;)
  87. 			p[--cnt[c[k][pn[i]]]]=pn[i];
  88. 		w=0;
  89. 		c.push_back(vector<int>(n));
  90. 		for(int i=0;i<n;i++)
  91. 		{
  92. 			if(i==0 || c[k][p[i]] != c[k][p[i-1]]) {
  93. 				w++;
  94. 			} else {
  95. 				int i1 = p[i]   + h; if(i1>=n) i1-=n;
  96. 				int i2 = p[i-1] + h; if(i2>=n) i2-=n;
  97. 				if(c[k][i1]!=c[k][i2]) w++;
  98. 			}
  99. 			c[k+1][p[i]] = w-1;
  100. 		}
  101. 	}
  102.  
  103. 	// the answer is all substrings minus sum lcp of neighboring suffixes
  104. 	LL ans = ((LL)n*(n-1))/2;
  105. 	for(int k=1;k<n;k++)
  106. 	{
  107. 		// calculating lcp of neighboring suffixes
  108. 		// again refer to e-maxx.ru :D
  109. 		int i=p[k];
  110. 		int j=p[k-1];
  111. 		int cur = 0;
  112. 		for (int h=c.size(); h--;)
  113. 			if (c[h][i] == c[h][j]) {
  114. 				cur += 1<<h;
  115. 				i += 1<<h;
  116. 				j += 1<<h;
  117. 			}
  118. 		ans-=cur;
  119. 	}
  120. 	return ans;
  121. }
  122.  
  123.  
  124. int main() {
  125.     scanf("%s",s);
  126.     int n=strlen(s);
  127.     s[n]='$';
  128.     scanf("%s",s+n+1);
  129.     int m=strlen(s+n+1);
  130.     LL ans1=substr_count(n+1,s);
  131.     LL ans2=substr_count(m+1,s+n+1);
  132.     LL ans3=substr_count(n+m+2,s)-(LL)(1+n)*(1+m);
  133.     LL ans=2*ans3-ans1-ans2;
  134.     printf("%lld\n",ans);
  135. 	return 0;
  136. }
  137.  
Success #stdin #stdout 0s 3196KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/cw4N1Z
language:
C++ (gcc 8.3)
created:
11 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!