Introduction to competitive programming

Trie can insert and search string in O(L) time where L is the length of string,this is much faster than hashtable and binary search tree implementations. Trie Node consist of a collection of Trie nodes and a boolean flag to check whether node is leaf or not.

Tutorial Links

Also Topcoder had excellent explanation about TRIE

Here is the C++ implementation of above Algorithm

/*
  TRIE implementation in C++
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ALPHABET_SIZE 26
using namespace std;
struct Node
{
 struct Node *child[ALPHABET_SIZE];
 bool isLeaf;
};
struct Node *createNode()
{
 Node *nw=new Node;
 for(int i=0;i<26;i++)
  nw->child[i]=NULL;
 nw->isLeaf=0;
 return nw;
}
void addWord(struct Node *root,string s)
{
 int len=s.length();
 struct Node *temp=root;
 for(int i=0;i<len;i++)
 {
  int c=s[i]-'a';
  if(temp->child[c]==NULL)
  {
   temp->child[c]=createNode();
  }
  temp=temp->child[c];
 }
 temp->isLeaf=1;
}
bool search(struct Node *root,string s)
{
 int len=s.length();
 struct Node *temp=root;
 for(int i=0;i<len;i++)
 {
  int c=s[i]-'a';
  if(temp->child[c]==NULL)
   return false;
  temp=temp->child[c];
 }
 if(temp->isLeaf)
  return true;
 else
  return false;
}
void printAllStrings(struct Node *root,string s)
{
 if(!root)
  return;
 if(root->isLeaf)
 {
  cout<<s<<"\n";
  return;
 }
 else
 {
  for(int i=0;i<26;i++)
  {
   if(root->child[i])
   {
 
    printAllStrings(root->child[i],s+(char)('a'+i));
   }
  }
 }
}
int main()
{
 struct Node *root=createNode();
 addWord(root,"abcd");
 addWord(root,"ace");
 if(search(root,"sai"))
  cout<<"Sai found\n";
 else
  cout<<"Sai not found\n";
 if(search(root,"abcd"))
  cout<<"abcd found\n";
 else
  cout<<"abcd not found\n";
 printAllStrings(root,"");
}
 

Problem:

Link

#include<bits/stdc++.h>
using namespace std;
class Solution 
{
    public:
    bool isPalindrome(int x) 
    {
        if(x<0)
 return false;
 stringstream ss;
 ss<<x;
 string s1="",s,temp;
 s=ss.str();
 for(int i=0;i<s.length();i++)
 {
  if(s[i]!=' ')
  s1+=s[i];
 }
 temp=s1;
 reverse(s1.begin(),s1.end());
 return s1==temp?true:false;
    }
};
int main()
{
 Solution s;
 cout<<s.isPalindrome(131)<<endl;
 cout<<s.isPalindrome(-456)<<endl;
}

Problem:

This problem can be solved using kmp prefix function

Below is the working code for above problem

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
void prefix(char *s,int n,int *pref)
{
 int x,y;
 int j=0,i;
 pref[0]=0;
 for(int i=1;i<n;i++)
 {
  while(j>0 && s[j]!=s[i])
  j=pref[j-1];
  if(s[i]==s[j]) 
  j++;
  pref[i]=j;
 }
 int ans=1;
 x=n-pref[n-1];
 if(n%x==0)
 ans=n/x;
 printf("%d\n",ans); 
}
int main()
{
 
 char pat[100005];
 scanf("%s",pat);
 while(strcmp(pat,"*")!=0)
 {
 int n=strlen(pat);
 int pref[n+1];
 prefix(pat,n,pref);
 scanf("%s",pat);
 }
} 

Problem:

Here is given a simple problem related to string matching often called as a needle in a haystack

This problem is easily solved with Kmp algorithm

Below is the working code for above problem

#include<cstdio>
#include<cstring>
using namespace std;
char pat[1000010];
char text[1000010];
int pref[1000010];
void prefix(char *s)
{
 int n=strlen(s),flag=1;
 int j=0,i;
 pref[0]=0;
 for(int i=1;i<n;i++)
 {
  while(j>0 && s[j]!=s[i])
  j=pref[j-1];
  if(s[i]==s[j]) 
  j++;
  pref[i]=j;
 }
 
 
}
void search(char *text,char *pat)
{
 int len=strlen(text),flag=1;
 int m=strlen(pat);
 int j=0;
 for(int i=0;i<len;i++)
 {
  while(j>0 && text[i]!=pat[j])
  j=pref[j-1];
  if(text[i]==pat[j])
  j++;
  if(j==m)
  {
  printf("%d\n",i-m+1);
  j=pref[j-1];
  }
 }
 if(flag==1)
        printf("\n");
}
int main()
{
 int n;
 while(scanf("%d\n",&n)!=EOF)
        {
      memset(pref,0,sizeof(pref));
      scanf("%s",pat);
  prefix(pat);
  scanf("%s",text);
  search(text,pat);
 }
 
}