Pagini recente » Cod sursa (job #1367916) | Cod sursa (job #608898) | Cod sursa (job #1951875) | Cod sursa (job #1381265) | Cod sursa (job #2430760)
//#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <fstream>
#define f(i,L,R) for (int i = (L); i < (R); ++i)
#define fe(i,L,R) for (int i = (L); i <= (R); ++i)
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const vector<unsigned> compute_lps(const string& pattern)
{
vector<unsigned> lps(pattern.size());
lps[0] = 0;
unsigned i = 1, j = 0;
while (i < pattern.size())
{
if (pattern[i] == pattern[j])
{
j++;
lps[i++] = j;
}
else
{
if (j == 0)
{
lps[i] = 0;
i++;
}
else
j = lps[j - 1];
}
}
return lps;
}
int main()
{
compute_lps("ABCDEABCF");
string pattern, text;
fin >> pattern >> text;
auto lps = compute_lps(pattern);
unsigned i = 0, j = 0, nr_of_matches = 0;
vector<unsigned> matched_pos;
while (i < text.length())
{
if (text[i] == pattern[j])
{
i++;
j++;
}
if (j == pattern.length())
{
if(nr_of_matches < 1000)
matched_pos.push_back(i - j);
nr_of_matches++;
j = lps[j - 1];
}
else if (i < text.length() && text[i] != pattern[j])
{
if (j == 0)
i++;
else
j = lps[j - 1];
}
}
fout << nr_of_matches << "\n";
for (auto& pos : matched_pos)
fout << pos << " ";
}