Pagini recente » Cod sursa (job #2438971) | Cod sursa (job #237736) | Cod sursa (job #1433409) | Cod sursa (job #245037) | Cod sursa (job #1435677)
#include<fstream>
#include<string>
using namespace std;
int* prefix(string p, int m)
{
int *f = new int[m + 1];
f[0] = -1;
int k;
for (int j = 1; j < m; j++)
{
k = f[j - 1];
while (k != -1 && p[j - 1] != p[k])
k = f[k];
f[j] = k + 1;
}
return f;
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string p, s;
f >> p >> s;
const int m = p.size(), n = s.size();
int *F = new int[m + 1];
F = prefix(p, m);
int i, j;
i = j = 0;
int sol = 0, v_sol[1001];
while (i < n)
{
while (j != -1 && s[i] != p[j])
j = F[j];
if (j == m - 1 && sol<1000){ sol++; v_sol[sol] = i - m + 1; j = 0; }
else
{
i++; j++;
}
}
g << sol << "\n";
for (i = 1; i <= sol; i++)
g << v_sol[i] << " ";
}