Pagini recente » Cod sursa (job #1850085) | Cod sursa (job #128741) | Cod sursa (job #2989775) | Cod sursa (job #3280467) | Cod sursa (job #1711666)
#include <string>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
static const int MAXN = 2000009;
int kmp_prefix[MAXN];
vector<int> pos;
bool matches(char a, char b)
{
bool result = a == b || a == '*' || b == '*';
return result;
}
void compute_prefix(const string& s)
{
kmp_prefix[0] = 0;
for (int i = 1; i < s.length(); i++)
{
bool found = false;
for (int tmp = kmp_prefix[i - 1]; tmp != 0; tmp = kmp_prefix[tmp - 1])
{
if (matches(s[tmp], s[i]))
{
kmp_prefix[i] = tmp + 1;
found = true;
break;
}
}
if (!found)
{
if (matches(s[i], s[0]))
{
kmp_prefix[i] = 1;
}
else
{
kmp_prefix[i] = 0;
}
}
}
}
int count_matches(const string& t, const string& p)
{
int match_count = 0;
compute_prefix(p);
int len = 0;
for (int i = 0; i + p.size() <= t.size(); i += (len == 0 ? 1 : len - kmp_prefix[len - 1]))
{
for (int j = len = kmp_prefix[len - 1]; j < p.size(); j++)
{
if (matches(t[i + j], p[j]))
{
len++;
}
else
{
break;
}
}
if (len == p.size())
{
match_count++;
if (match_count <= 1000)
{
pos.push_back(i);
}
}
}
return match_count;
}
int main()
{
string t, p;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f >> p >> t;
g << count_matches(t, p) << '\n';
for (int i = 0; i < pos.size(); i++)
{
g << pos[i] << ' ';
}
g << endl;
g.close();
return 0;
}