KMP algorithm for String Matching

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int pi[10000];
void prefix(char *p)
{
    int m=strlen(p);
    int k=0;
    pi[0]=0;
    for(int q=1;q<m;q++)
    {
        while(k>0 && p[k]!=p[q])
        {
            k=pi[k-1];
        }
        if(p[k]==p[q])
        {
            k++;
        }
        pi[q]=k;
    }
}
int main()
{
    int m;
    while(scanf("%d",&m)!=EOF)
    {
        char p[m];
        cin>>p;
        int q=0;
        prefix(p);
        char c;
        int flag=0;
        c=getchar();
        for(int i=0;;i++)
        {
            c=getchar();
            if(c=='\n')
            {
                if(i<m)
                {
                    cout<<"\n";
                    break;    
                }
                break;
            }
            while(q>0 && p[q]!=c)
            {
                q=pi[q-1];
            }
            if(p[q]==c)
                q++;
            if(q==m)
            {
                cout<<i-m+1<<endl;
                q=pi[q-1];
            }
        }
        if(flag)
            break;
    }
}

Miller Rabin Algorithm for Prime Generation

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
long long mulmod(long long a,long long b,long long c){u
    long long x = 0,y=a%c;
    while(b > 0){
        if(b%2 == 1){
            x = (x+y)%c;
        }
        y = (y*2)%c;
        b /= 2;
    }
    return x%c;
}
int modulo(int a,int b,int c){
    long long x=1,y=a; 
    while(b > 0){
        if(b%2 == 1){
            x=(x*y)%c;
        }
        y = (y*y)%c;
        b /= 2;
    }
    return x%c;
}
bool Miller(long long p,int iteration){
    if(p<2){
        return false;
    }
    if(p!=2 && p%2==0){
        return false;
    }
    long long s=p-1;
    while(s%2==0){
        s/=2;
    }
    for(int i=0;i<iteration;i++){
        long long a=rand()%(p-1)+1,temp=s;
        long long mod=modulo(a,temp,p);
        while(temp!=p-1 && mod!=1 && mod!=p-1){
            mod=mulmod(mod,mod,p);
            temp *= 2;
        }
        if(mod!=p-1 && temp%2==0){
            return false;
        }
    }
    return true;
}
int main()
{
        int t;
        long long m,n;
        cin>>t;
        while(t--)
        {
                cin>>m>>n;
                for(long long i=m;i<=n;i++)
                {
                        if(Miller(i,6))
                                cout<<i<<endl;
                }
                cout<<endl;
        }
}

Given graph is a tree or not?

You are given an unweighted, undirected graph. Write a program to check if it's a tree topology.

Input

The first line of the input file contains two integers N and M --- number of nodes and number of edges in the graph (0 < N <= 10000, 0 <= M <= 20000). Next M lines contain M edges of that graph --- Each line contains a pair (u, v) means there is an edge between node u and node v (1 <= u,v <= N). Output

Print YES if the given graph is a tree, otherwise print NO.

Example

Input:
3 2
1 2
2 3

Output:
YES


Solution:

A graph can be confirmed as a tree if and only if:

1)There are N-1 edges for N vertices
2)The Graph must be connected

#include <iostream>
#include <vector>
#include <set>
using namespace std;


#define MAX 100000
typedef vector<int> vi;
typedef vector<vi> vvi;

int N;
vvi W;//W stores the graph(Adjacency List)
vi V;//Array for storing whether a node is visited or not
set<int> s;// A set to store all the vertices.It is used to check if all
           // vertices are visited or not
void dfs(int i) 
{
        if(!V[i]) 
        { 
                vi::iterator it;
                V[i] = true;
                for(it=W[i].begin();it!=W[i].end();it++)
                        dfs(*it);
        }
} 

bool check_graph_connected_dfs(int s1) 
{ 
        int start_vertex = s1; 
        V = vi(MAX, false); 
        dfs(start_vertex);
        set<int>::iterator it; 
        for(it=s.begin();it!=s.end();it++)//check if any vertex in set is unvisited
        {
                if(V[*it]==0)
                        break;
        }
        if(it==s.end())
                return 1;
        else
                return 0;
}
int main()
{
        int v,e,v1,v2,temp;
        cin>>v>>e;
        vi::iterator it[MAX];
        if(e!=v-1)
        {
                cout<<"NO"<<endl;
                return 0;
        }
        W.resize(MAX);
        for(int i=0;i<MAX;i++)
        {
                it[i]=W[i].begin();
        }
        for(int i=0;i<e;i++)
        {
                cin>>v1>>v2;
                s.insert(v1);
                s.insert(v2);
                temp=v1;
                it[v1]=W[v1].insert(it[v1],v2); 
                it[v2]=W[v2].insert(it[v2],v1); 
        }
        if(check_graph_connected_dfs(temp))
                cout<<"YES"<<endl;
        else
                cout<<"NO"<<endl;
        return 0;
}

Combination of strings

The Program prints all the different combinations of a given string.

The input is:
s-The String
n-The length of combinations.

#include <iostream>
#include <cstring>
using namespace std;

void combination(string str,int len)
{
        int start=0;
        int k=0;
        int sec=0;
        for(start=0;start<=str.length()-len;start++)
        {
                sec=start;
                k=0;
                while(sec+len<=str.length())
                {
                        k++;
                        sec=start+k;
                        cout<<str[start];
                        for(int j=0;j<len-1;j++)
                                cout<<str[sec+j];
                        cout<<" ";
                }
                cout<<endl;
        }
}


int main()
{
        string s;
        int n;
        cin>>s;
        cin>>n;
        combination(s,n);
}

Why is the size of an empty class not zero?

To ensure that the addresses of two different objects will be different. For the same reason, "new" always returns pointers to distinct objects. Consider:

class Empty { };

void f()
{
  Empty a, b;
  if (&a == &b) 
    cout << "impossible: report error to compiler supplier";

  Empty* p1 = new Empty;
  Empty* p2 = new Empty;
  if (p1 == p2) cout << "impossible: report error to compiler supplier";
} 

There is an interesting rule that says that an empty base class need not be represented by a separate byte:

struct X : Empty 
{
  int a;
  // ...
};

void f(X* p)
{
  void* p1 = p;
  void* p2 = &p->a;
  if (p1 == p2) 
    cout << "nice: good optimizer";
}

This optimization is safe and can be most useful. It allows a programmer to use empty classes to represent very simple concepts without overhead. Some current compilers provide this "empty base class optimization".

Can I call a virtual function from a constructor?

Yes, but be careful. It may not do what you expect. In a constructor, the virtual call mechanism is disabled because overriding from derived classes hasn't yet happened. Objects are constructed from the base up, "base before derived".
Consider:

#include<string>
#include<iostream>
using namespace std;
class B 
{
public:
  B(const string& ss)
  { 
    cout << "B constructor\n"; 
    f(ss);
  }

  virtual void f(const string&) 
  { cout << "B::f\n";
  }
};

class D : public B
{
public:
  D(const string & ss) :B(ss) 
  {
    cout << "D constructor\n";
  }
  void f(const string& ss) 
  {
    cout << "D::f\n"; s = ss; 
  }
private:
  string s;
};

int main()
{
  D d("Hello");
}

the program compiles and produce
B constructor
B::f
D constructor
Note not D::f. Consider what would happen if the rule were different so that D::f() was called from B::B(): Because the constructor D::D() hadn't yet been run, D::f() would try to assign its argument to an uninitialized string s. The result would most likely be an immediate crash.
Destruction is done "derived class before base class", so virtual functions behave as in constructors: Only the local definitions are used - and no calls are made to overriding functions to avoid touching the (now destroyed) derived class part of the object.

For more details see D&E 13.2.4.2 or TC++PL3 15.4.3.

It has been suggested that this rule is an implementation artifact. It is not so. In fact, it would be noticeably easier to implement the unsafe rule of calling virtual functions from constructors exactly as from other functions. However, that would imply that no virtual function could be written to rely on invariants established by base classes. That would be a terrible mess.

Why don't we have virtual constructors?

A virtual call is a mechanism to get work done given partial information. In particular, "virtual" allows us to call a function knowing only an interfaces and not the exact type of the object. To create an object you need complete information. In particular, you need to know the exact type of what you want to create. Consequently, a "call to a constructor" cannot be virtual.
Techniques for using an indirection when you ask to create an object are often referred to as "Virtual constructors". For example, see TC++PL3 15.6.2.
For example, here is a technique for generating an object of an appropriate type using an abstract class:

struct F 
{
  // interface to object creation functions
  virtual A* make_an_A() const = 0;
  virtual B* make_a_B() const = 0;
};

void user(const F& fac)
{
  A* p = fac.make_an_A(); // make an A of the appropriate type
  B* q = fac.make_a_B(); // make a B of the appropriate type
  // ...
}

struct FX : F 
{
  A* make_an_A() const { return new AX(); } // AX is derived from A
  B* make_a_B() const { return new BX(); } // BX is derived from B
};

struct FY : F 
{
  A* make_an_A() const { return new AY(); } // AY is derived from A
  B* make_a_B() const { return new BY(); } // BY is derived from B
};

int main()
{
  FX x;
  FY y;
  user(x); // this user makes AXs and BXs
  user(y); // this user makes AYs and BYs

  user(FX()); // this user makes AXs and BXs
  user(FY()); // this user makes AYs and BYs
  // ...
}

This is a variant of what is often called "the factory pattern". The point is that user() is completely isolated from knowledge of classes such as AX and AY.