We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
In my solution I didn't end up relying on sorting, only on hashing, to help reduce the set of string positions that I need to examine. Then I do a full, expensive verify for each of those positions. It passes the tests but just barely. Room for improvement.
#include<vector>#include<iostream>#include<unordered_map>usingnamespacestd;// Two subranges that are similar will always give same hashinthash_subrange_similar(conststring&s,intstart,intlen){unsignedlonghash=5381;intsimilar_map[11]={0};intcount=1;for(inti=start;i<start+len;i++){intc=s[i];if(similar_map[c]==0){similar_map[c]=count;count++;}hash=hash*similar_map[c]+33;}return(int)hash;}// Test if s[i..i+len] and s[j..j+len] are similar substringsboolare_similar(conststring&s,inti,intj,intlen){intsimilar_map_i[11]={0};intsimilar_map_j[11]={0};for(intk=0;k<len;k++){intci=s[i+k];intcj=s[j+k];if(similar_map_i[ci]==0&&similar_map_j[cj]==0){similar_map_i[ci]=cj;similar_map_j[cj]=ci;}elseif(similar_map_i[ci]!=cj||similar_map_j[cj]!=ci){returnfalse;}}returntrue;}intmain(){ints_len,num_tests;cin>>s_len>>num_tests;strings;cin>>s;// Reduce characters to 1-10 range (reserve 0 for "unknown")for(inti=0;i<s.length();i++){s[i]=s[i]-'a'+1;}// To speed things up we start by creating an index:// we hash the first 12 characters at each position and// then track for each hash which positions match that hash.constinthash_length=12;unordered_map<int,vector<int>>index;for(inti=0;i<=(int)s.length()-hash_length;i++){inthash=hash_subrange_similar(s,i,hash_length);index[hash].push_back(i);}for(inti=0;i<num_tests;i++){intstart,end;cin>>start>>end;intquery_start=start-1;// start is 1-basedintquery_len=end-start+1;// start/end are inclusiveintcount=0;if(query_len>=hash_length){// Hash first 12 chars of query then use index to get possible matching positionsinthash=hash_subrange_similar(s,query_start,hash_length);for(intj:index[hash]){if(j<=s.length()-query_len){if(are_similar(s,query_start,j,query_len)){count++;}}}}else{// Brute force for short queriesfor(intj=0;j<=s.length()-query_len;j++){if(are_similar(s,query_start,j,query_len)){count++;}}}cout<<count<<endl;}return0;}
Similar Strings
You are viewing a single comment's thread. Return to all comments →
In my solution I didn't end up relying on sorting, only on hashing, to help reduce the set of string positions that I need to examine. Then I do a full, expensive verify for each of those positions. It passes the tests but just barely. Room for improvement.