solving linear equation by matrix normalization method

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int a[4],b[4],c[4],e[4];

    char buff[10];

    string str;

    int m=1,n=1,l=1,k=1,h=0,d=0;
    int flag=0;

    for(int i=0; i<3; i++)
    {
        getline(cin,str);

        d=0,flag=0;

        for(int j=0; j<str.size(); j++)
        {
            if(str[j]=='-') flag=1;

            else if(str[j]>='0' and str[j]<='9') buff[d++]=str[j];

            else if(str[j]=='=' or str[j]=='+' or str[j]==' ') continue;

            else if(str[j]=='x')
            {
                buff[d++]=NULL;

                h=atoi(buff);

                if(h==0) h=1;
                if(flag==1) h=-h;

                a[m++]=h;

                memset(buff,NULL,sizeof(buff));
                d=0;
                flag=0;

            }
            else if(str[j]=='y')
            {
                buff[d++]=NULL;

                h=atoi(buff);

                if(h==0) h=1;
                if(flag==1) h=-h;

                b[n++]=h;

                memset(buff,NULL,sizeof(buff));
                d=0;
                flag=0;

            }
            else if(str[j]=='z')
            {
                buff[d++]=NULL;

                h=atoi(buff);

                if(h==0) h=1;
                if(flag==1) h=-h;

                c[l++]=h;

                memset(buff,NULL,sizeof(buff));
                d=0;
                flag=0;
            }

        }
        buff[d++]=NULL;
        h=atoi(buff);


        if(flag==1) h=-h;

        e[k++]=h;

        memset(buff,NULL,sizeof(buff));
        d=0;
        flag=0;
    }

    double a11,a12,a13,a21,a22,a23,a31,a32,a33,x1,x2,x3,c1,c2,c3,y1,y2,y3;

    a11=a[1],a21=a[2],a31=a[3];
    a12=b[1],a22=b[2],a32=b[3];
    a13=c[1],a23=c[2],a33=c[3];

    c1=e[1],c2=e[2],c3=e[3];


    double l21,l31,l32,u11,u12,u13,u22,u23,u33;

    u11=a11;
    u12=a12;
    u13=a13;

    l21=a21/u11;

    u22=a22-(l21*u12);

    u23=a23-(l21*u13);

    l31=a31/u11;

    l32=(a32-(l31*u12))/u22;

    u33=a33-(l31*u13)-(l32*u23);

    y1=c1;

    y2=c2-(l21*y1);

    y3=c3-(l31*y1)-(l32*y2);

    x3=(y3/u33);

    x2=(y2-(u23*x3))/u22;

    x1=(y1-((u12*x2)+(u13*x3)))/u11;

    cout<<x1<<endl<<x2<<endl<<x3;
}

1258 - Making Huge Palindromes

Problem Link: http://lightoj.com/volume_showproblem.php?problem=1258

Solution idea :

Consider the 4th test case
P = anncbaaababaaa
Let
Q = aaababaaabcnna (reverse of P)
Now look how can we construct the shortest palindrome by adding character to the
right of P,
with the help of Q
P : anncbaaababaaa|||||
Q : |||||aaababaaabcnna
Ans:anncbaaababaaabcnna
So all we need to do is search for the longest prefix of Q in P.
You can do this by using KMP.

Solution :

#include<bits/stdc++.h>

using namespace std;

int f[1000002];

void kmp_preprocess(string pattern)
{
    int m=pattern.size();
    f[0]=0;

    int j=0;

    for(int i=1;i<m;i++)
    {
        if(pattern[i]==pattern[j])
        {
            f[i]=j+1;
            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];
                if(pattern[i]==pattern[j])
                {
                    f[i]=j+1;
                    j++;
                    break;
                }
            }
        }
    }
}

int kmp(string text,string pattern)
{
    int j=0;

    int n=text.size();
    int m=pattern.size();

    for(int i=0;i<n;i++)
    {
        if(text[i]==pattern[j])
        {

            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];

                if(text[i]==pattern[j])
                {
                    j++;
                    break;
                }
            }
        }
    }
    return j;
}


int main()
{

string text,pattern;

 int n,p,q;
 scanf("%d",&n);

 for(int ca=1;ca<=n;ca++)
 {
     cin>>text;

     pattern=text;
     reverse(pattern.begin(),pattern.end());
     memset(f,0,sizeof(f));
    kmp_preprocess(pattern);

     p=kmp(text,pattern);
     q=pattern.size();
     q=2*q - p ;
     printf("Case %d: %d\n",ca,q);
 }


}

1255 - Substring Frequency / kmp source code 2

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1255

Solve :

#include<bits/stdc++.h>
#define ll long long

using namespace std;

ll int f[1000003];

void kmp_preprocess(string pattern)
{
    ll int m=pattern.size();
    f[0]=0;

    ll int j=0;

    for(ll int i=1;i<m;i++)
    {
        if(pattern[i]==pattern[j])
        {
            f[i]=j+1;
            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];
                if(pattern[i]==pattern[j])
                {
                    f[i]=j+1;
                    j++;
                    break;
                }
            }
        }
    }
}

ll int  kmp(string text,string pattern)
{
   ll int j=0,cnt=0;

    ll int n=text.size();
    ll int m=pattern.size();

    for(ll int i=0;i<n;i++)
    {
        if(text[i]==pattern[j])
        {
            j++;
            if(j==m)
            {
                cnt++;
                j=f[j-1];
            }

        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];

                if(text[i]==pattern[j])
                {
                    j++;
                    break;
                }
            }
        }
    }
    return cnt;
}


int main()
{
   string text,pattern;
   ll int t,n=0;
   scanf("%lld",&t);

for(ll int ca=1;ca<=t;ca++)
{
      cin>>text>>pattern;
      memset(f,0,sizeof(f));
      kmp_preprocess(pattern);
      n=kmp(text,pattern);
      printf("Case %lld: %lld\n",ca,n);

}

}

10679 - I Love Strings!!

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1620

Solution :

#include<bits/stdc++.h>

using namespace std;

int f[1000000];

void kmp_preprocess(string pattern)
{
    int m=pattern.size();
    f[0]=0;

    int j=0;

    for(int i=1;i<m;i++)
    {
        if(pattern[i]==pattern[j])
        {
            f[i]=j+1;
            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];
                if(pattern[i]==pattern[j])
                {
                    f[i]=j+1;
                    j++;
                    break;
                }
            }
        }
    }
}

bool kmp(string text,string pattern)
{
    int j=0;

    int n=text.size();
    int m=pattern.size();

    for(int i=0;i<n;i++)
    {
        if(text[i]==pattern[j])
        {
            if(j==m-1) return true;
            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];

                if(text[i]==pattern[j])
                {
                    j++;
                    break;
                }
            }
        }
    }
    return false;
}


int main()
{

   int k,q;

   scanf("%d",&k);
   string text,pattern;

   while(k--)
   {
      cin>>text;

       scanf("%d",&q);

       while(q--)
       {
           cin>>pattern;
           kmp_preprocess(pattern);

            bool n;

          n=kmp(text,pattern);

          if(n==1) cout<<"y"<<endl;
          else cout<<"n"<<endl;

       }
   }


}

KMP source code 1

Tutorial :

1. https://tanvir002700.wordpress.com/2015/03/03/kmp-knuth-morris-pratt-algorithm/#more-556

2. https://returnzerooo.wordpress.com/2016/09/08/kmp/

3. https://www.youtube.com/watch?v=GTJr8OvyEVQ

4. https://www.youtube.com/watch?v=KG44VoDtsAA



source code :

#include<bits/stdc++.h>

using namespace std;

int f[1000000];

void kmp_preprocess(string pattern)
{
    int m=pattern.size();
    f[0]=0;

    int j=0;

    for(int i=1;i<m;i++)
    {
        if(pattern[i]==pattern[j])
        {
            f[i]=j+1;
            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];
                if(pattern[i]==pattern[j])
                {
                    f[i]=j+1;
                    j++;
                    break;
                }
            }
        }
    }
}

bool kmp(string text,string pattern)
{
    int j=0;

    int n=text.size();
    int m=pattern.size();

    for(int i=0;i<n;i++)
    {
        if(text[i]==pattern[j])
        {
            if(j==m-1) return true;
            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];

                if(text[i]==pattern[j])
                {
                    j++;
                    break;
                }
            }
        }
    }
    return false;
}


int main()
{
   string text,pattern;

   cin>>text>>pattern;

    kmp_preprocess(pattern);

    bool n;

    n=kmp(text,pattern);

    cout<<n;

}