KMP - algorithm for string matching
complexity of compute prefix function O(m) ,where m is length of the pattern
complexity of KMP is O(n)
Reference-Coreman 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int pie[500];
char *pattern;
char *text;
int m;  //length is pattern
int n;  //length of text
void compute_prefix()
{
    cin>>pattern+1;
    cin>>text+1;
     m=strlen(pattern+1);
    int k=0;
    pie[1]=0;
    for(int q=2;q<=m;q++)
    {
        while(k>0&&pattern[k+1]!=pattern[q])
        {
            k=pie[k];
          
        }
        if(pattern[k+1]==pattern[q])
            k=k+1;
        pie[q]=k;

    }
}
void kmp_matching()
{

     compute_prefix();
     n=strlen(text+1);
     int q=0;
     for(int i=1;i<=n;i++)
     {
         while(q>0&&pattern[q+1]!=text[i])
         {
             q=pie[q];
         }
         if(pattern[q+1]==text[i])
             q=q+1;
         if(q==m)
         {
             printf("pattern occurs with shift %d\n",i-m);
             q=pie[q];
         }
     }

}

int main()
{

    pattern=new char[500];
    text=new char[1000];
        kmp_matching();
    return 0;
}

Matrix_exponential Template use for solving recurrence relation

/* Template of matrix exponential written by Rahul Kumar Singh (selfcompiler) date :19-oct-2012 time --8:41 P.M. */
/* ~~~~~~~~**@#*#@**~~~~~~~~~*/
#include<cstdio>
#include<iostream>
#include<math.h>
#include<vector>
#include<utility>
#include<map>
using namespace std;
#define K 3 
//size of matrix using 1 based index not 0'!!!!! ........
#define LIMIT 10000000000000
//maximum value of n
#define MODULO 1000000007
// modulo value
#define ll long long int
/*matrix structure */
struct MATRIX{
        ll mat[K+1][K+1];
    MATRIX()  //constructor
    {
        for(int i=0;i<=K;i++)
            for(int j=0;j<=K;j++)
                mat[i][j]=0;
    }//end constructor
    void print_matrix() //print matrix
    {
        for(int i=1;i<=K;i++)
        {
            for(int j=1;j<=K;j++)
                cout<<mat[i][j]<<" ";
            cout<<std::endl;
        }
    } //end print matrix

};//end of matrix structre
/* main program start here */
int main()
{
    struct MATRIX A;  
    ll column[K+1]={0,1,1,1};  //column vector to find the answer
    A.mat[1][1]=1,A.mat[1][2]=1,A.mat[1][3]=1;  //transformation matrix of 3 X 3 (1 based index)
    A.mat[2][1]=1,A.mat[2][2]=0;A.mat[2][3]=0;
    A.mat[3][1]=0,A.mat[3][2]=1,A.mat[3][3]=0;
    map<int,struct MATRIX> I;
    I[1]=A;  //transformation matrix
        ll next=2,p=1,p1,p2;
while(next<=LIMIT)    //precomputation of matrix of power 1,2,4,8,16,.......
{
             MATRIX object;
         p1=p2=p;
         for(int i=1;i<=K;i++)    //matrix multiplication start
         for(int j=1;j<=K;j++)
             for(int k=1;k<=K;k++)
             {
                  object.mat[i][j]+=(I[p1].mat[i][k]*I[p2].mat[k][j])%MODULO;
                  if(object.mat[i][j]>=MODULO)
                           object.mat[i][j]%=MODULO;

             }//matrix multipliaction end
         I[next]=object;
         p=next;
         next=next*2;
               
}//end of precomputation
    ll tc,n,count=0,pw2;
    cin>>tc;
    ll term[K+1]={0,1,1,1};     //r=q+w+e;   //term[1]>term[2]>term[3];
while(tc--)
{
    cin>>n;
    MATRIX obj;
        count=1;
                if(n>=4)
        {
        n=n-3;
        while(n)  //compute matrix of power n
        {


                     ll x=n&-n;  //farthest set bit of n
                          if(count)  
              {      //first encounter for initialization
                                 count=0;  
                 obj=I[x];

              }
              else
              {
                    MATRIX temp;  //make a temp object
                 for(int i=1;i<=K;i++)// matrix multipliaction
                 for(int j=1;j<=K;j++)
                     for(int k=1;k<=K;k++)
                         {
                           temp.mat[i][j]+=(I[x].mat[i][k]*obj.mat[k][j])%MODULO;
                           if(temp.mat[i][j]>=MODULO)
                           temp.mat[i][j]%=MODULO;
                         }//matrix multipliaction end
                obj=temp;
              }
              n=n-x;
        ll ans=0;
        for(int i=1;i<=K;i++)  //compute answer
        {
            ans+=(column[i]*obj.mat[1][i])%MODULO;
            if(ans>=MODULO)
                ans%=MODULO;
        }// finally computed
             cout<<ans<<std::endl;
        }
        else
        {
            cout<<term[n]<<std::endl;
        }

}

         return 0;
}

   
 // complexity O(logN)

CLASSIFIACTION OF EDGES IN GRAPH 

EDGES OF A DIRECTED GRAPH CAN BE DIVIDE INTO FOUR GROUPS 

1.Tree Edge 

2.Back Edge 

3.Forward Edge 

4.Cross Edge                

TREE EDGE :

an edge included in the DFS spanning forest.

BACK EDGE :

an edge to a vertex to its spanning tree ancestor.  

FORWARD EDGE :

an edge from a vertex to a spanning tree non son descendant.

CROSS EDGE :

an edge between two vertices is a cross edge when there is no ancestor and descendant relationship between them in spanning forest.

code to identify the edges

static int time=0;

void DFS(int v)

{

int i;

time++;

d[v]=time;

state[v]=visited;

for(i=0;i<n;i++)

{

     if(adj[v][i]==1)

       {

          if(state[i]==initial)

              {

              cout<<"Tree Edge :"<<v<<" "<<i<<"\n";

              DFS(i);

               }

            else if(state[i]==visited)

               { 

                   cout<<"Back Edge :"<<v<<" "<<i<<"\n";    

                }

              else if(d[v]<d[i])

                  cout<<"Forward Edge :"<<v<<" "<<i<<"\n";

                else

                  cout<<"Cross Edge :"<<v" "<<i<<"\n";

              }

     }

state[v]=finished;

  f[v]=++time;

return ;

}

THIS IS DEPTH FIRST SEARCH (WAY TO TRAVERSE A GRAPH)  DFS!!!!!!!!!!
THERE IS TWO APPROACHES TO DO IT 
1:- ITERATIVE APPROACH
2:-RECURSIVE APPROACH 
APPLICATION:- FINDING CONNECTED COMPONENTS
           :-TOPOLOGICAL SORTING
           :-FINDING BRIDGE ON A GRAPH
           :-FIND STRONGLY CONNECTED COMPONENTS
           :-FINDING BICONNECTIVITY IN GRAPH
   LINK TO STUDY :-DFS wiki link

CODE OF ITERATIVE APPROACH 
#include<iostream>
#include<stack>
#include<vector>
#include<stdio.h>
using namespace std;
#define MAX 100
#define initial 1
#define visited 2
int n;/* number of nodes in the graph*/
int adj[MAX][MAX]; //adjancency matrix
int state[MAX]; /*can be visited or initial*/
stack<int> stac_k;
void create_graph()   //create a graph //
{
int i,o,d,max_edge;
printf("enter the number of nodes\n");
scanf("%d",&n);
max_edge=n*(n-1);
       for(i=1;i<=max_edge;i++)
         {
          printf("enter the edge %d:(-1,-1 to quit) ",i);
          scanf("%d%d",&o,&d);
          if((o==-1)&&(d==-1))
          break;
          if((o>=n)||(d>=n)||(o<0)||(d<0))
          {cout<<"invalid edge";i--;}
          else
          adj[o][d]=1;
         }
return ;
}
void display_graph()  //display graph
{
           for(int i=0;i<n;i++)
           {
           for(int j=0;j<n;j++)
           {
           if(adj[i][j]==1)
           cout<<"1";
           else
           cout<<"0";
           }
           cout<<endl;
           }
return;
}
void DFS(int v)
{
  int i;
  stac_k.push(v);
  while(!stac_k.empty())
   {
     v=stac_k.top();
        stac_k.pop();
               if(state[v]==initial)
              {
                   state[v]=visited;
                   cout<<v<<":->";
               }
               for(i=n-1;i>=0;i--)
              {
                   if((state[i]==initial)&&(adj[v][i]==1))
                   stac_k.push(i);
              }
  }
return ;
}
void df_traversal()
{
   int v=0;
   for(v=0;v<n;v++)
    state[v]=initial;
   printf("enter starting vertex for DFS\n");
   scanf("%d",&v);
   DFS(v);
return ;
}
int main()
{
create_graph();
display_graph();
df_traversal();
return 0;
}

well this is my first blog !!! 
first :-my name:- RAHUL SINGH
myintrest:-coding,take participation in programming contest;
what topics i discuss here untill the end is algorithms,programming questions ,data structures,c,c++ 
MY CODECHEF PROFILE