fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());
  4. const int N = 5e6 + 1;
  5. char c[N + 5];
  6. string a,b;
  7. int z[N + 1];
  8. long long ans;
  9. int main(){
  10. 	// freopen("input.txt","r",stdin);
  11. 	freopen("ultron.in","r",stdin);
  12. 	freopen("ultron.out","w",stdout);
  13. 	scanf("%s",c);
  14. 	a = c;
  15. 	scanf("%s",c);
  16. 	b = c;
  17. 	for(auto &i : a)i = tolower(i);
  18. 	for(auto &i : b)i = tolower(i);
  19. 	string s = a + '#' + b;
  20. 	int l = 0,r = 0;
  21. 	for(int i = 1;i < s.size();i++)
  22. 		if(r < i){
  23. 			l = r = i;
  24. 			while(r < s.size() && s[r] == s[r - l])r++;
  25. 			z[i] = r - l;
  26. 			r--;
  27. 		}
  28. 		else{
  29. 			int x = i + z[i - l];
  30. 			if(x > r){
  31. 				l = i;
  32. 				while(r && s[r] == s[r - l])r++;
  33. 				z[i] = r - l;
  34. 				r--;
  35. 			}
  36. 			else z[i] = z[i - l];
  37. 		}
  38. 	for(int j = a.size() + 1;j < s.size();j++){
  39. 		int bst = z[j];
  40. 		int i = j - a.size() - 1;
  41. 		if(bst != -1)ans+=(bst + 1LL)*bst/2 + bst*1LL*(b.size() - i - bst);
  42. 	}
  43. 	printf("%lld\n",ans);
  44. }
Success #stdin #stdout 0s 39656KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fQXzia
language:
C++14 (gcc 8.3)
created:
4 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!