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;

}

1289 - LCM from 1 to n

Problem link : http://lightoj.com/volume_showproblem.php?problem=1289

Tutorial : https://nlognblog.wordpress.com/2015/12/01/light-oj1289-lcm-from-1-to-n/

Hint : 

1. When a problem says that you have to do modulo 2^32 (and it requires only addition, subtraction and multiplication) then just take them as unsigned integers and do regular operations. Just think that the compiler uses 32 bit operations, and if it overflows, then the most significant bits will be lost but the least significant 32 bits will be correct, which is equivalent to modulo 2^32.

Solution :

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

using namespace std;

const int MAX = 100000000;  // 10^8
const int LMT =     10000;  // sqrt(MAX)

int _c[(MAX>>6)+1];

int  primes[5761482];

#define IsComp(n)  (_c[n>>6]&(1<<((n>>1)&31)))

#define SetComp(n) _c[n>>6]|=(1<<((n>>1)&31))
ll mnt=0;
void sieve()
{
    int x=0;

    for (int i = 3; i <= LMT; i += 2)
        if (!IsComp(i))
            for (int j = i*i; j <= MAX; j += i+i)
                SetComp(j);

    primes[x++]=2;
    mnt++;
    for (int i=3; i <= MAX; i += 2)
        if (!IsComp(i))
        {
            primes[x++]=i;
            mnt++;
        }
}

ll store[5761482];

void precal()
{
    store[0]=2;

    for(ll i=1; i<mnt; i++)
    {
        store[i]=store[i-1]*primes[i];
    }
}
ll cal(ll n)
{
    ll temp,ret=1;

    for(ll i=0; primes[i]*primes[i]<=n; i++)
    {
        temp=n;
        temp=temp/primes[i];
        while(temp>=primes[i])
        {
            temp=temp/primes[i];
            ret=ret*primes[i];
        }
    }
    return ret;

}

int main()
{
    ll  n,val,sq,q,rs,cnt,ans,t,ca=1;
    sieve();
    precal();
    scanf("%u",&t);

    while(t--)
    {
        scanf("%u",&n);

        ans=cal(n);

        val=upper_bound(primes,primes+mnt,n)-primes;
        val--;
        ans=ans*store[val];

        printf("Case %u: %u\n",ca,ans);
        ca++;
    }
}

10680 - LCM

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

Solution Idea : http://pavelsimo.blogspot.com/2012/06/uva-10680-lcm.html

Solution :

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

using namespace std;

bool status[1000002];

vector<ll int>prime;

void sieve()
{
    ll int n=1000000;
    ll int sq=sqrt(n);

    for(ll int i=4; i<=n; i=i+2) status[i]=true;

    prime.push_back(2);

    for(ll int i=3; i<=sq; i=i+2)
    {
        if(status[i]==false)
        {
            for(int j=i*i; j<=n; j=j+i) status[j]=true;
        }
    }
    status[1]=1;
    status[0]=1;

    for(ll int i=3; i<=n; i=i+2)
    {
        if(status[i]==0) prime.push_back(i);
    }
}

ll int fact[1000005];

int main()
{
    ll int n,val,sq,q,rs,cnt,ans;
    sieve();
    while(scanf("%lld",&n) and n)
    {
        memset(fact,0,sizeof(fact));

        fact[1]=1;
        ans=1;
        for(ll int j=0; j<prime.size() and prime[j]<=n; j++)
        {
            val=prime[j];

            while(val<=n)
            {
                val=val*prime[j];

            }
            val=val/prime[j];
            fact[prime[j]]=val;

        }

        ll int cc=fact[5];
        cnt=0;
        while(fact[5]>1)
        {
            fact[5]=fact[5]/5;
            cnt++;
        }
        for(ll int k=cnt; k>0; k--)
        {
            fact[2]=fact[2]/2;
        }
        for(int i=1; i<=1000000; i++)
        {
            if(fact[i]!=0) ans=((ans%10)*(fact[i]%10))%10;
        }
        printf("%lld\n",ans);
    }

}

11388 - GCD LCM

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

Solution Idea : http://blog.forthright48.com/2015/08/uva-11388-gcd-lcm.html

Solution :

#include<bits/stdc++.h>

#define ll long long

using namespace std;

int main()

{

    ll int ca,g,l,a,b;

    scanf("%lld",&ca);

    while(ca--)

    {

        scanf("%lld%lld",&g,&l);

        if(l%g!=0)

        {

            printf("-1\n");

        }

        else

        {

            a=g;

            b=l;

            printf("%lld %lld\n",a,b);

        }

    }

}