Pagini recente » Cod sursa (job #483888) | Cod sursa (job #439091) | Cod sursa (job #2749526) | Cod sursa (job #1028172) | Cod sursa (job #929379)
Cod sursa(job #929379)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
typedef vector<int>::iterator iter;
vector<int> prefix(const string& str)
{
vector<int> pi(str.size(), 0);
int k = 0;
for (int i = 1; i < str.size(); ++i) {
while (k > 0 && str[i] != str[k])
k = pi[k - 1];
if (str[i] == str[k])
++k;
pi[i] = k;
}
return pi;
}
vector<int> match(const string& str, const string& patt)
{
vector<int> matches;
vector<int> pi = prefix(patt);
int k = 0;
for (int i = 0; i < str.size(); ++i) {
while (k > 0 && str[i] != patt[k])
k = pi[k - 1];
if (str[i] == patt[k])
++k;
if (k == patt.size())
matches.push_back(i - patt.size() + 1);
}
return matches;
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string str, patt;
fin >> patt >> str;
vector<int> matches = match(str, patt);
fout << static_cast<int>(matches.size()) << endl;
for (iter it = matches.begin(); it != matches.end(); ++it)
fout << *it << " ";
fout << endl;
return 0;
}