fork(28) download
copy 
  1. #include <string>
  2. #include <vector>
  3. #include <iostream>
  4.  
  5. using namespace std;
  6.  
  7. int longestBorder(const string& s) {
  8. 	int len = s.length();
  9. 	vector<int> prefixFunc(len); 
  10. 	prefixFunc[0] = 0;
  11.  
  12. 	int curBorderLen = 0;	
  13. 	for (int i = 1; i < len; ++i) {	
  14. 		while (curBorderLen > 0 && s[curBorderLen] != s[i]) 
  15. 			curBorderLen = prefixFunc[curBorderLen - 1]; 
  16.  
  17. 		if (s[curBorderLen] == s[i]) 
  18.             ++curBorderLen;
  19.  
  20.   		prefixFunc[i] = curBorderLen;
  21.    	}
  22.  
  23.    	return prefixFunc[len-1];
  24. }
  25.  
  26. int main() {
  27. 	string s;
  28. 	cin >> s;
  29. 	cout << longestBorder(s) << endl;
  30. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
abracadabra
stdout
copy 
4
https://ideone.com/hTW8FL
language:
C++ (gcc 8.3)
created:
7 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!