Pagini recente » Cod sursa (job #2341821) | Cod sursa (job #697003) | Cod sursa (job #2328595) | Cod sursa (job #1631266) | Cod sursa (job #2803490)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
/**
* KMP[i] = lungimea celui mai lung prefix care este si sufix in s[0...i]
*
* KMP[i] = a => s[0...(a-1)] = s[(i-a+1)...i]
*/
vector <int> KMP(string s)
{
// Adaugam la misto un caracter, ca sa fie indexat de la 1
s = "$" + s;
vector <int> pi(s.size());
// K = pi[i - 1]
int k = 0;
for (int i = 2; i < (int)s.size(); i++) {
// Cat timp nu avem match
while (k != 0 && s[i] != s[k + 1])
k = pi[k];
// Am gasit un match
if (s[i] == s[k + 1])
k++;
// Daca NU am gasit match, conform while-ului, stim ca K=0
pi[i] = k;
}
// Re-indexam de la 0
pi.erase(pi.begin());
return pi;
}
/**
* Gaseste inceputul matchurilor lui s in t.
*/
vector <int> FindMatches(string s, string t)
{
string to_kmp = s + "$" + t;
vector <int> kmp = KMP(to_kmp);
vector <int> ans;
for (int i = (int)s.size() + 1; i < (int)kmp.size(); i++)
if (kmp[i] == (int)s.size())
ans.push_back(i - 2 * (int)s.size());
return ans;
}
int main()
{
string s,t;
fin >> s;
fin >> t;
vector <int> ans = FindMatches(s,t);
fout << ans.size() << '\n';
for(auto i : ans)
fout << i << ' ';
fout << '\n';
}