Pagini recente » Cod sursa (job #2799906) | Cod sursa (job #2975399) | Cod sursa (job #2424485) | Cod sursa (job #1956658) | Cod sursa (job #2718660)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
int N, M;
void calculatePrefixVector(string& pattern, vector<int>& prefixVector)
{
prefixVector[0] = 0;
int len = 0;
for (int i = 1; i < N;)
{
if (pattern[i] == pattern[len])
{
len++;
prefixVector[i] = len;
i++;
}
else
{
if (len != 0)
{
len = prefixVector[len - 1];
}
else
{
prefixVector[i] = 0;
i++;
}
}
}
}
void solve(string& pattern, string& space, int& K, vector<int>& solutions)
{
vector<int> prefixVector(N);
calculatePrefixVector(pattern, prefixVector);
int j = 0;
for (int i = 0; i < M;)
{
if (pattern[j] == space[i])
{
i++;
j++;
}
else
{
if (j > 0)
{
j = prefixVector[j - 1];
}
else
{
i++;
}
}
if (j == N)
{
j = prefixVector[j - 1];
K++;
solutions.push_back(i - N);
}
}
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
// Program
string pattern, space;
f >> pattern >> space;
N = pattern.size();
M = space.size();
int K = 0;
vector<int> solutions;
solve(pattern, space, K, solutions);
g << K << endl;
int toShow = min(K, 1000);
for (int i = 0; i < toShow; i++)
{
g << solutions[i] << " ";
}
// Exit
f.close();
g.close();
return 0;
}