Pagini recente » Cod sursa (job #1893307) | Cod sursa (job #2513711) | Cod sursa (job #2970454) | Cod sursa (job #1029962) | Cod sursa (job #2662930)
#include <fstream>
#include <string.h>
#include <vector>
using namespace std;
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[2000000], ch;
int N, A_index = -1, B_index = -1, CONTOR = 0;
vector<int> prefix, SOL;
f.getline(A, 2000001);
N = strlen(A);
prefix.push_back(-1);
for(int i = 1; i < N; i++)
{
int aux = prefix.back() + 1;
if(A[i] == A[aux])
prefix.push_back(aux);
else
prefix.push_back(-1);
}
while(f >> ch)
{
B_index++;
while(A_index > -1 && A[A_index + 1] != ch)
A_index = prefix[A_index];
if(A[A_index + 1] == ch)
A_index++;
if(A_index == N - 1)
{
if(CONTOR < 1000)
SOL.push_back(B_index - N + 1);
CONTOR++;
A_index = prefix[A_index];
}
}
g << CONTOR << '\n';
if(CONTOR > 1000)
CONTOR = 1000;
for(int i = 0; i < CONTOR; i++)
g << SOL[i] << ' ';
return 0;
}