Pagini recente » Cod sursa (job #3238392) | Cod sursa (job #888150) | Cod sursa (job #465905) | Cod sursa (job #1795462) | Cod sursa (job #3238217)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
vector <int> sol;
vector <int> prefix(string s)
{
int n = (int)s.length();
vector <int> kmp(n);
for (int i = 1; i < n; i++)
{
int j = kmp[i-1];
while (j > 0 && s[i] != s[j])
j = kmp[j - 1];
if (s[i] == s[j])
j ++;
kmp[i] = j;
}
return kmp;
}
vector <int> matching(string s, string t)
{
string c = s + '!' + t;
vector <int> lg = prefix(c);
vector <int> poz;
for (int i = s.size() + 1; i < c.size(); i ++)
{
if (lg[i] >= s.size())
poz.push_back(i - s.size());
}
return poz;
}
int main()
{
string a, b;
cin >> a >> b;
sol = matching(a, b);
cout << sol.size() << '\n';
for (int i = 0; i < min((int)sol.size(), 1000); i ++)
cout << sol[i] - a.size() << " ";
return 0;
}