fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4.  
  5. const char* wordsArr1[] = {"baseball", "mansion", "backpack" };
  6. const char* wordsArr2[] = {"baseb", "mansi", "backp" };
  7.  
  8. /**given some word1, some word2, and minLength which is the value min(strlen(word1), strlen(word2))
  9. this will return true iff the first 5 chars or more of word1 and word2 match, otherwise false.
  10. It is safe to modify this to up to 7 char matching, any more overflows the uint64_t into sign
  11. bit which is undefined.**/
  12. bool matches(const char* word1, const char* word2, int minLength)
  13. {
  14. 	if(minLength < 5) //experiment with removing this, branching may be slower
  15. 		return false;
  16.  
  17. 	uint64_t concatenatedChars1 = 0;
  18. 	uint64_t concatenatedChars2 = 0;
  19.  
  20. 	// no loop due to loop unrolling, might provide speedups in case of cache misses
  21. 	concatenatedChars1 |= (uint8_t)word1[0];
  22. 	concatenatedChars2 |= (uint8_t)word2[0];
  23.  
  24. 	concatenatedChars1 <<= 8;
  25. 	concatenatedChars2 <<= 8;
  26.  
  27. 	concatenatedChars1 |= (uint8_t)word1[1];
  28. 	concatenatedChars2 |= (uint8_t)word2[1];
  29.  
  30. 	concatenatedChars1 <<= 8;
  31. 	concatenatedChars2 <<= 8;
  32.  
  33. 	concatenatedChars1 |= (uint8_t)word1[2];
  34. 	concatenatedChars2 |= (uint8_t)word2[2];
  35.  
  36. 	concatenatedChars1 <<= 8;
  37. 	concatenatedChars2 <<= 8;
  38.  
  39. 	concatenatedChars1 |= (uint8_t)word1[3];
  40. 	concatenatedChars2 |= (uint8_t)word2[3];
  41.  
  42. 	concatenatedChars1 <<= 8;
  43. 	concatenatedChars2 <<= 8;
  44.  
  45. 	concatenatedChars1 |= (uint8_t)word1[4];
  46. 	concatenatedChars2 |= (uint8_t)word2[4];
  47.  
  48. 	return concatenatedChars1 == concatenatedChars2;
  49. }
  50.  
  51. int main() {
  52. 	for(int i = 0; i < 3; i++)
  53. 	{
  54. 		const char* word1 = wordsArr1[i]; 
  55. 		for(int j = 0; j < 3; j++)
  56. 		{
  57. 			const char* word2 = wordsArr2[j];
  58. 			std::cout << matches(word1, word2, std::min(strlen(word1), strlen(word2))) << std::endl;
  59. 		}
  60. 	}
  61. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
0
0
0
1
0
0
0
1
https://ideone.com/iBshBt
language:
C++14 (gcc 8.3)
created:
6 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!