Substring with Concatenation of All Words

时间:2022-12-01 16:54:57


#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdint.h>
#include <sys/wait.h>
#include <limits.h>
#include <time.h>
#include <pthread.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <queue>
#include <sstream>
#include <iterator>
#include <algorithm>
#include <thread>
using namespace std;
vector<int> &findSubstring(const string &s, vector<string>&words)
{
int i;
string line;
static vector<int>indices;
vector<int>tmpvec;
indices.clear();
if(s.empty())
{
cerr << "s is none...!" << endl;
return indices;
}
int size = words.size();
if(!size)
{
cerr << "words is none...!" << endl;
return indices;
}
tmpvec.resize(size);
for(i = 0;i < size;i++) tmpvec[i] = i;
do
{
// join the words to line
line.clear();
for(i = 0;i < size;i++)
{
int index = tmpvec[i];
line += words[index];
}
// find line in the s
{
int pos = s.find(line, 0);
if(pos == string::npos) continue;
int len = line.size();
do
{
indices.push_back(pos);
pos = s.find(line, pos + len);
}while(pos != string::npos);
}
}while(next_permutation(tmpvec.begin(), tmpvec.end()));

return indices;

}
int main()
{
string s = "barfoofoobarthefoobarman";
vector<string>words;
words.push_back("bar");
words.push_back("foo");
words.push_back("the");
vector<int>&rs = findSubstring(s, words);
copy(rs.begin(), rs.end(), ostream_iterator<int>(cout, " "));
cout << endl;

return 0;
}

CC=g++
all:
$(CC) -std=c++11 -g -o hello helloC++.cpp -pthread -lpthread