Pagini recente » Cod sursa (job #1103301) | Cod sursa (job #1053264) | Cod sursa (job #2831027) | Cod sursa (job #2746647) | Cod sursa (job #2662899)
#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 = 0, 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)
{
CONTOR++;
SOL.push_back(B_index - N + 1);
A_index = prefix[A_index];
if(CONTOR == 1000)
break;
}
}
g << CONTOR << '\n';
for(int i = 0; i < CONTOR; i++)
g << SOL[i] << ' ';
return 0;
}