Pagini recente » Cod sursa (job #2911031) | Atasamentele paginii Clasament sth_cute | Cod sursa (job #596558) | Cod sursa (job #1656424) | Cod sursa (job #2456824)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int table[2000005];
int main()
{
string A, B;
ios_base::sync_with_stdio(false);
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin >> A >> B;
A = " " + A;
B = " " + B;
int N = A.size() - 1;
int M = B.size() - 1;
table[1] = 0;
for (int i = 2,k=0; i <= N; ++i)
{
while (k !=0 && A[k + 1] != A[i])
{
k = table[k];
}
if (A[k + 1] == A[i])
{
++k;
}
table[i] = k;
}
vector<int> sol;
int nr_sol = 0;
for (int j = 1,i=0; 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);
}
}
}
cout << nr_sol << "\n";
for (auto i : sol)
cout << i << " ";
cout << "\n";
return 0;
}