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.

```
#include <iostream>
```
```
#include <vector>
```
```
#include <string>
```
```
 
```
```
using namespace std;
```
```
 
```
```
int main()
```
```
{
```
```
    int n1,n2,ans,pos,flag;
```
```
    string s1, s2;
```
```
    cout<<"Enter the string s1 ";
```
```
    cin >> s1;
```
```
    cout<<"Enter the string s2 ";
```
```
    cin>> s2;
```
```
    n1=s1.length();
```
```
    n2=s2.length();
```
```
 
```

    vector< vector<int> > l(n1 + 1, vector<int>(256, n1));

    //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

```
 
```
```
    for (int i = n1 - 1; i >= 0; i--)
```
```
    {
```

        for (char j = 'a'; j <= 'z'; j++)

```
        {
```
```
            if (s1[i] == j)
```
```
                l[i][j] = i;
```
```
 
```
```
            else if (i + 1 < n1)
```
```
                l[i][j] = l[i + 1][j];
```
```
 
```
```
        }
```
```
 
```
```
    }
```
```
 
```
```
    ans = 1;
```
```
    pos = 0;
```
```
    flag=1;
```
```
 
```

    for (int i = 0; i < n2 && flag; i++)

```
    {
```
```
        pos = l[pos][s2[i]];
```
```
 
```
```
        if (pos == n1)
```
```
        {
```
```
            ans++;
```
```
            pos = 0;
```
```
            pos = l[pos][s2[i]];
```
```
 
```
```
            if (pos == n1)
```
```
            {
```

                cout<<"Impossible"<<endl;

```
                flag=0;
```
```
            }
```
```
        }
```
```
 
```
```
        pos++;
```
```
    }
```
```
 
```
```
    if(flag)
```
```
    {
```

        cout<<"Minimum number newspaper headings required to obtaing string s2 is "<<endl;

```
        cout<<ans<<endl;
```
```
    }
```
```
 
```
```
    return 0;
```
```
}
```

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.

Subscribe Now: Dynamic Programming Newsletter | Important Subjects Newsletters

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.

« Prev - Parentheses Expressions Problem – Catalan Numbers

» Next - Triangle Problem using Dynamic Programming

Related Posts:

Recommended Articles: