Pagini recente » Cod sursa (job #3224531) | Cod sursa (job #1120991) | Cod sursa (job #2382021) | Cod sursa (job #2553629) | Cod sursa (job #2418968)
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int main()
{
string s, p;
f >> p >> s;
vector<int> pref(p.size(), 0);
int i = 0, j = 1;
while (j < p.size())
if (p[i] == p[j])
pref[j] = i + 1,
++i, ++j;
else if (i == 0)
++j;
else
i = pref[i - 1];
vector<int> matches;
i = 0, j = 0;
while (i < s.size())
if (j == p.size())
{
matches.push_back(i - j);
j = pref[j - 1];
}
else if (s[i] == p[j])
++i, ++j;
else if (j == 0)
++i;
else
j = pref[j - 1];
if (j == p.size())
matches.push_back(s.size() - p.size());
g << matches.size() << '\n';
if(matches.size() > 1000)
matches.resize(1000);
for (auto x : matches)
g << x << ' ';
return 0;
}