UVA 10567: Helping Fill Bates

UVA 10567: Helping Fill Bates

Simple Version

Given an original sequence S and N ≤ 3501 other sequences T1, T2, T3, ... TN, test if each of the N sequences are a subsequence of S. If so, also state the leftmost location of the first element of the sequence in S, along with the leftmost location of the last element of the sequence in S.

The Algorithm

We are given a sequence and we are asked to determine if it is a subsequence of S or not. Let the sequence be Q. For a Q to be a subsequence of S, every element Q[i] of Q must be also found in S, and every element Q[i] and Q[j] where i<j (i is before j) must also be found in S in the same order.

The "in the same order" statement is VERY important: it determines what algorithm to use. If we did not need it to be found in the same order, meaning S and Q can be randomly shuffled and Q is still a subseq. of S, we can simply use hash tables to keep track of the count how many of each letter there is. However, we need to use binary search to keep track of where a item is, for order matters.

My Code

#include <algorithm>

#include <string>

#include <vector>

#include <iostream>

using namespace std;

vector<vector<int>> ls;

int main()

{

ls.resize(256);

ios_base::sync_with_stdio(0);

string all; cin >> all;

for(int i=0;i<all.size();i++) ls[all[i]].push_back(i);

int q; cin>>q;

for(int i=0; i<q;i++)

{

string x;

cin >> x;

int ind = -1, a = 0;

bool fin = true;

for(int j=0; j<x.size(); j++)

{

auto low = upper_bound(ls[x[j]].begin(), ls[x[j]].end(), ind);

ind = low - ls[x[j]].begin();

if(low == ls[x[j]].end())

{

fin = false;

break;

}

ind = ls[x[j]][ind];

if(j==0) a = ind;

}

if(fin) printf("Matched %d %d\n",a, ind);

else printf("Not matched\n");

}

}