Pagini recente » Cod sursa (job #2705205) | Cod sursa (job #1701472) | Cod sursa (job #1701474) | Cod sursa (job #1480361) | Cod sursa (job #2456813)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
int N, M;
void prefix_table(vector<int> &table, string A)
{
table[1] = 0;
int i = 0;
for (int j =2; j <= N; ++j)
{
while (i > 0 && A[i + 1] != A[j])
{
i = table[i];
}
if (A[i + 1] == A[j])
{
++i;
}
table[j] = i;
}
}
void KMP(int*nr_sol,vector<int> &sol, vector<int> table, string A, string B)
{
int i = 0;
for (int j = 1; j <= M; j++)
{
while (i > 0 && A[i + 1] != B[j])
{
i = table[i];
}
if (A[i + 1] == B[j])
{
++i;
}
if (i == N)
{
if (sol.size() < 1000)
{
(*nr_sol)++;
sol.push_back(j - N);
}
}
}
}
int main()
{
string A, B;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin >> A >> B;
A = " " + A;
B = " " + B;
N = A.length() - 1;
M = B.length() - 1;
vector<int> table(N+1);
prefix_table(table, A);
vector<int> sol;
int nr_sol = 0;
KMP(&nr_sol,sol, table, A, B);
cout << nr_sol << endl;
for (auto i : sol)cout << i << " ";
return 0;
}