Strings

May 29, 2020 DSA

Types:

• Manipulation: mainly string methods and functions
• DP problems: LCS, Regex
• String algos: KMP algo, Z algo, Manacher’s algo

KMP

Mainly used for pattern search, say pattern P, string S.

• STL .find() uses O(n*m)
• KMP uses O(n+m)

Blackbox: KMP(s) -> kmp[] Ex KMP(“abcababcada”): kmp[]: [0,0,0,1,2,1,2,3,4,0,1]

kmp[i] denotes length of longest proper suffix thats also a proper prefix for string s[0..1]. proper means less than the complete string property: kmp(i+1) <= kmp(i)+1 (next element increases by atmost one)

vector<int> kmp(string s)
{
   int n = s.length();
   vi kmp(n);
   int i=0,j=-1;
   kmp[0]=-1;
   while(i<n)
   {
      while(j!=-1 and s[i]!=s[j]) j=kmp[j];
      j++;i++;
      kmp[i] = j;
   }
   for(int i=0;i<=n;i++)
   {
      cout<<kmp[i]<<" ";
   }
   return kmp;
}