Pagini recente » Cod sursa (job #1295118) | Cod sursa (job #2541032) | Cod sursa (job #3160159) | Cod sursa (job #115391) | Cod sursa (job #3029952)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int> matches(string s, int target)
{
// lps[i] este lungimea celui mai lung prefix care este si sufix al sirului pana la index i
vector<int> lps(s.size());
lps[0] = 0;
vector<int> sol;
for (int i = 1; i < s.size(); i++)
{
int cur = lps[i - 1];
while (cur && s[i] != s[cur])
cur = lps[cur - 1];
if (s[i] == s[cur])
cur++;
lps[i] = cur;
if (lps[i] == target)
sol.push_back(i - 2 * target);
}
return sol;
}
int main()
{
string a, b;
fin >> a >> b;
string c = a + "#" + b;
// pattern + "#" + șirul în care căutăm
vector<int> sol = matches(c, a.size());
fout << sol.size() << "\n";
if (sol.size() > 1000)
sol.resize(1000);
for (int x : sol)
fout << x << " ";
fout << "\n";
return 0;
}