Pagini recente » Cod sursa (job #177480) | Cod sursa (job #125789) | Cod sursa (job #2562776) | Cod sursa (job #2187730) | Cod sursa (job #1092714)
//Include
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
FILE *in, *out;
//Constante
const int sz = (int)2e6+1;
//Functii
void failure_function();
//Variabile
char str[sz], sub[sz];
int strLen, subLen, answer;
int prefix[sz];
char answers[sz];
//Main
int main()
{
in = fopen("strmatch.in", "rt");
out = fopen("strmatch.out", "wt");
fscanf(in,"%s%s",sub+1, str+1);
strLen = strlen(str+1);
subLen = strlen(sub+1);
failure_function();
int currentPrefix = 0;
for(int i=1; i<=strLen; ++i)
{
while(currentPrefix && sub[currentPrefix+1] != str[i])
currentPrefix = prefix[currentPrefix];
if(sub[currentPrefix+1] == str[i])
++currentPrefix;
if(currentPrefix == subLen)
{
if(++answer <= 1000)
answers[answer] = i - subLen;
currentPrefix = prefix[currentPrefix];
}
}
fprintf(out, "%d\n", answer);
int limit = min(answer, 1000);
for(int i=1; i<=limit; ++i)
fprintf(out,"%d ", answers[i]);
fclose(in);
fclose(out);
return 0;
}
void failure_function()
{
int currentPrefix = 0;
for(int i=2; i<=subLen; ++i)
{
while(currentPrefix && sub[currentPrefix+1] != sub[i])
currentPrefix = prefix[currentPrefix];
if(sub[currentPrefix+1] == sub[i])
++currentPrefix;
prefix[i] = currentPrefix;
}
}