Newspaper Headline Problem using Dynamic Programming

This is a C++ Program that Solves the Newspaper Headline Problem using Dynamic Programming technique.

Problem Description

A newspaper is published in Walrusland. Its heading is s1, it consists of lowercase Latin letters.
Fangy the little walrus wants to buy several such newspapers, cut out their headings, glue them one to another in order to get one big string. After that walrus erase several letters from this string in order to get a new word s2. It is considered that when Fangy erases some letter, there’s no whitespace formed instead of the letter. That is, the string remains unbroken and it still only consists of lowercase Latin letters.

Problem Solution

In this problem, our objective is to find how many instances of string s1 we will need to build to string s2. We will create a matrix l to memoize values. This is initialized as follows :

l[i][j] will contain first occurrence of character j in the string s1[i…n1-1].
If j is not in s1[i…n1-1], l[i][j]=n1.

Expected Input and Output

Case-1:

s1="abc"
s2="bcac"
 
Expected result=2 
If we take two such headings and glue them one to the other one, we get "abcabc". If we erase the letters on positions 1 and 5, we get a word "bcac".
Program/Source Code

Here is source code of the C++ Program to Solve the Newspaper Headline Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

advertisement
advertisement
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. int main()
  8. {
  9.     int n1,n2,ans,pos,flag;
  10.     string s1, s2;
  11.     cout<<"Enter the string s1 ";
  12.     cin >> s1;
  13.     cout<<"Enter the string s2 ";
  14.     cin>> s2;
  15.     n1=s1.length();
  16.     n2=s2.length();
  17.  
  18.     vector< vector<int> > l(n1 + 1, vector<int>(256, n1));
  19.     //l[i][j] will contain first occurrence of character j in the string s1[i...n1-1]
  20.     //if j is not in s1[i...n1-1], l[i][j]=n1
  21.  
  22.     for (int i = n1 - 1; i >= 0; i--)
  23.     {
  24.         for (char j = 'a'; j <= 'z'; j++)
  25.         {
  26.             if (s1[i] == j)
  27.                 l[i][j] = i;
  28.  
  29.             else if (i + 1 < n1)
  30.                 l[i][j] = l[i + 1][j];
  31.  
  32.         }
  33.  
  34.     }
  35.  
  36.     ans = 1;
  37.     pos = 0;
  38.     flag=1;
  39.  
  40.     for (int i = 0; i < n2 && flag; i++)
  41.     {
  42.         pos = l[pos][s2[i]];
  43.  
  44.         if (pos == n1)
  45.         {
  46.             ans++;
  47.             pos = 0;
  48.             pos = l[pos][s2[i]];
  49.  
  50.             if (pos == n1)
  51.             {
  52.                 cout<<"Impossible"<<endl;
  53.                 flag=0;
  54.             }
  55.         }
  56.  
  57.         pos++;
  58.     }
  59.  
  60.     if(flag)
  61.     {
  62.         cout<<"Minimum number newspaper headings required to obtaing string s2 is "<<endl;
  63.         cout<<ans<<endl;
  64.     }
  65.  
  66.     return 0;
  67. }
Program Explanation

In the main function, we take input for strings s1 and s2. Then, we fill the memoization matrix in bottom up manner and display the result on standard output.

Runtime Test Cases
 
Case-1:
$ g++ newspaper_headline.cpp
$ ./a.out
Enter the string s1 abcd
Enter the string s2 dabc
Minimum number newspaper headings required to obtaing string s2 is 
2

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

advertisement
If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.