Pagini recente » Cod sursa (job #2445289) | Cod sursa (job #3259746) | Cod sursa (job #142846) | Cod sursa (job #555038) | Cod sursa (job #2472374)
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#define NMAX 100010
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s, a;
int prefix[NMAX];
vector<int> sol;
void makePrefix()
{
int q = 0;
prefix[1] = 0;
for (int i = 2; i < s.size(); i++)
{
while (q && s[i] != s[q + 1])
q = prefix[q];
if (s[i] == s[q+1])
q++;
prefix[i] = q;
}
}
int main()
{
fin >> s >> a;
s = "#" + s;
a = "#" + a;
makePrefix();
int N = s.size() - 1;
int M = a.size() - 1;
int q = 0;
for (int i = 1; i <= M; i++)
{
while (q && s[q + 1] != a[i])
q = prefix[q];
if (s[q + 1] == a[i])
q++;
if (q == N)
{
sol.push_back(i-N+1);
q = prefix[N];
}
}
fout << sol.size() << '\n';
for (int i = 0; i < sol.size() && i < 1000; i++)
{
fout << sol[i]-1 << ' ';
}
return 0;
}