What can I do to speed up this code (String Similarity)?
c++, string
Solution
Your current code computes for a single string for length L, in `O(L^3)` (substr takes linear running time). Not to mention high constant costs to the above complexity due to inefficient passing around of strings.
Your algorithm can be simply reduced to finding longest common prefixes of a string with all its suffixes. This can be easily done using Suffix Aray. The concept cannot be explained as an answer, so I will highly recommend you to read this.
A sub optimal and simple to code Suffix Array solution will have `O(Llg^2(L))` (L = string length) construction time and `O(1)` time to query Longest Common Prefix of 2 suffixes using Range Minimum Query. Note that the whole string itself is its own suffix. In your case, you need to make L queries for each string. So total complexity for one string will be `O(Llg^2(L)) + O(L)`.
If you want to improve further, You may reduce the construction time to `O(Llg(L))` by using radix sort, or to `O(L)` (Read)
Problem
This is a code written in C++ using standard libraries to find the String Similarity of a string S with each of it's suffixes. Though, it gives the correct output, it takes a lot of time in doing so for large strings. Here's the code: ``` #include <iostream> #include <string> using namespace std; int sim(string a, string b){ int count=0; int sa=a.size(); int sb=b.size(); int iter; if(sa>sb) iter=sb; else iter=sa; for(int i=0; i<iter; i++){ if (a[i]!=b[i]) break; else count++; } return count; } int strsim(string a){ int sum=0; int s=a.size(); for(int i=0; i<s; i++){ sum=sum+sim(a,a.substr(i)); } return sum; } int main(){ int n; cin >> n; string a[n]; for(int i=0; i<n; i++){ cin >> a[i]; } for(int i=0; i<n; i++){ cout << strsim(a[i]) << '\n'; } } ``` Constraints: The length of each string is at most 100000 and contains only lower case characters and the number of testcases, 'n' cannot exceed 10. Sample I/O: Input: ``` 1 ababaa ``` Output: ``` 11 ``` i.e, `6 + 0 + 3 + 0 + 1 + 1 = 11`