CareerCup

There can be two cases
1.Where all given patterns are of equal length.
In this case the idea is maintain a hashMap where keys would be given patterns and value would be its count.Before streaming starts insert all keys in to the hashMap.Now maintain a queue of length of the pattern which stores the stream character,whenever a new character comes, add this to the queue and remove the character present at the front one.After this check if the value of the queue is present in the hashMap as a key or not and if its present increment by 1.
Case 2: When given patterns are of different size
Here maintain a buffer whose size is of longest pattern and at each character arrivals instead of checking whole buffer as key in hashMap check its all suffix as a key.

gf

public class PatternCount {

    int count = 0;

    public static void main(String args[]) {
        PatternCount patternCount = new PatternCount();
        int count = patternCount.findCount("0111000100", "00");
        System.out.println("Count  : " + count);
        
    }

    public int findCount(String str, String pattern) {
        System.out.println("Str : " + str + " : pattern :" + pattern);
        for (int i=0; i<str.length()-pattern.length()+1; i++) {
            String subStr = str.substring(i, i+pattern.length());
            System.out.println("sbuStr :" + subStr);
            if (subStr.equals(pattern)) count++;            
        }
        return count;
    }
}

public class PatternCount {

int count = 0;

public static void main(String args[]) {
PatternCount patternCount = new PatternCount();
int count = patternCount.findCount("0111000100", "00");
System.out.println("Count : " + count);

}

public int findCount(String str, String pattern) {
System.out.println("Str : " + str + " : pattern :" + pattern);
for (int i=0; i<str.length()-pattern.length()+1; i++) {
String subStr = str.substring(i, i+pattern.length());
System.out.println("sbuStr :" + subStr);
if (subStr.equals(pattern)) count++;
}
return count;
}
}

public class PatternCount {

    int count = 0;

    public static void main(String args[]) {
        PatternCount patternCount = new PatternCount();
        int count = patternCount.findCount("0111000100", "00");
        System.out.println("Count  : " + count);
        
    }

    public int findCount(String str, String pattern) {
        System.out.println("Str : " + str + " : pattern :" + pattern);
        for (int i=0; i<str.length()-pattern.length()+1; i++) {
            String subStr = str.substring(i, i+pattern.length());
            System.out.println("sbuStr :" + subStr);
            if (subStr.equals(pattern)) count++;            
        }
        return count;
    }
}

Approach 1

Take the P patterns and insert them all in a Trie data structure. Building the Trie would take O(P * L), where L is the length of the pattern. Then, start reading the stream, at each step i, 0 <= i < N, where N is the size of the stream, read the i-nth char. Keep a hash table that maps each i to a node in the Trie. At step i, add (i, trieRoot) to the hash table, then, for each value in the hash table, update the corresponding node by following edge labeled with the char read at that step. If a node pointer gets out of the boundary of the Trie, remove it's entry from the hash table, if you hit a node that represents a word, increase by one the matches for the pattern represented by such node. There are N steps and at each step you have to update O(N) pointers, so total time complexity would be O(P * L + N^2). Space complexity is O(P * L + N).

Approach 2

Read all the stream of N chars first. Build a Suffix Tree for the string represented by the N chars. Building the suffix tree would take O(N^2) time and space. Then for each of the P patterns, check how many times does it appears in the Suffix Tree in linear time. Time complexity of that would be O(N^2 + P * L), the same as approach 1!

Approach 3

Same as approach 2, but use Suffix Array instead. Building the Suffix Array would take O(N log N), which is faster.

For each size of the patterns we can have a sliding window. To find a match I used Rabin-Carp algorithm. Time is O(n * k), where n is number of characters we've read from the stream, and k is max size of the patterns.

#include <iostream>
#include <vector>
#include <list>
#include <unordered_map>

using namespace std;

class SlidingWindow {
	public:
		SlidingWindow()
		{
			size_ = 0;
			Clear();
		}

		SlidingWindow(int size)
		{
			size_ = size;
			Clear();
		}
		void CharIn(char c)
		{
			if (list_.size() == size_) {
				hash_ -= static_cast<uint64_t>(list_.front()) << ((size_ - 1) * 8);
				list_.pop_front();
			}
			hash_ = (hash_ << 8) | c;
			list_.push_back(c);
		}
		uint64_t Hash() const
		{
			return list_.size() == size_ ? hash_ : numeric_limits<uint64_t>::max();
		}
		void Clear()
		{
			hash_ = 0;
			list_.clear();
		}

	private:
		int size_;
		uint64_t hash_;
		list<char> list_;
};

vector<pair<string, int>> Counts(list<char> &stream, vector<string> const &patterns)
{
	unordered_map<int, SlidingWindow> size_to_window;
	unordered_map<uint64_t, pair<string, int>> hash_to_pattern;
	for (auto &p : patterns) {
		if (size_to_window.find(p.size()) == size_to_window.end()) {
			size_to_window[p.size()] = SlidingWindow(p.size());
		}
		SlidingWindow &w = size_to_window[p.size()];
		for (char c : p) {
			w.CharIn(c);
		}
		hash_to_pattern[w.Hash()] = pair<string, int>(p, 0);
		w.Clear();
	}

	while (!stream.empty()) {
		char c = stream.front();
		stream.pop_front();
		for (auto &el : size_to_window) {
			SlidingWindow &w = el.second;
			w.CharIn(c);
			auto it = hash_to_pattern.find(w.Hash());
			if (it != hash_to_pattern.end()) {
				++it->second.second;
			}
		}
	}

	vector<pair<string, int>> out;
	for (auto &el : hash_to_pattern) {
		out.push_back(el.second);
	}

	return out;
}

int main()
{
	list<char> stream = {'A', 'B', 'C', 'A', 'S', 'G', 'K', 'T', 'A', 'B', 'C', 'A', 'S', 'K', 'H', 'T'};
	vector<pair<string, int>> counts = Counts(stream, {"ABCAS", "ASGKT", "KHT"});
	for (auto &count : counts) {
		cout << count.first << "=>" << count.second << "\n";
	}
}