Given two strings a and b, find whether any anagram of string a is a sub-string of string b

I know this is a fairly (old and) simple question. But what people do not realize is that it has a catch! I saw this question here and browsed through most of the solutions. Almost all of them (except the crazy ones where folks wanted to do brutal force search) would fail on a very simple case. And this question, is all about just that case

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main() {
  string src, tgt;
  std::getline(cin, src);
  std::getline(cin, tgt);
  vector<int> buf(256, 0);
  const int tot = src.size();
  for (int i = 0; i < src.size(); ++i) {
    buf[src[i]]++;
  }
  vector<int> tmp(256, 0);
  int start = -1, tmp_tot = 0, end = 0;
  for (int i = 0; i < tgt.size(); ++i) {
    const unsigned char ch = tgt.at(i);
    if (buf[ch] > 0) {
      if (tmp[ch] == buf[ch]) {
        if (tmp_tot > 256) {
          tmp.clear();
          tmp.resize(256, 0);
        } else {
          while (tmp_tot > 0) tmp[tgt[i - tmp_tot--]]--;
        }
        start = i;
        tmp[ch]++;
        tmp_tot = 1;
      } else {
        if (start == -1) start = i;
        tmp[ch]++;
        ++tmp_tot;
        if (tmp_tot == tot) end = i;
      }
    }
  }
  if (end > 0) {
    cout << start << "    " << end << std::endl;
  } else {
    cout << "Not found\n";
  }
  return 0;
}
Advertisements

Find the longest sequence of prefix shared by all the words in a string

Source (I guess) This version has the minimum comparisons required for the solution.

#include&lt;algorithm&gt;
#include&lt;iostream&gt;
#include&lt;string&gt;
#include&lt;vector&gt;
using namespace std;
int main() {
  int n;
  cin &gt;&gt; n;
  vector&lt;string&gt; strs;
  while (n--) {
    string tmp;
    cin &gt;&gt; tmp;
    strs.push_back(tmp);
  }
  int len = 0;
  while (len < strs[0].size()) {
    char cur = strs[0].at(len);
    if (std::all_of(strs.begin() + 1,
                    strs.end(),
                    [len,cur](const string&amp; t) {
                        return len &lt; t.size() &amp;&amp; t.at(len) == cur; })) {
      ++len;
    } else {
      break;
    }
  }
  cout &lt;&lt; len &lt;&lt; std::endl;
  return 0;
}
%d bloggers like this: