Pagini recente » Cod sursa (job #2778640) | Cod sursa (job #1914832) | Cod sursa (job #1449995) | Cod sursa (job #2987090) | Cod sursa (job #1622277)
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;
char A[2000003];
char B[2000003];
int automat[2000003];
int a, b; //no need to know length for b though
queue<int> res;
void buildKMP(char *str)
{
int k = 0;
automat[1] = 0;
int it;
for (it = 2; str[it] != '\n'; ++it)
{
while (k > 0 && str[it] != str[k+1])
k = automat[k];
if (str[k+1] == str[it])
++k;
automat[it] = k;
}
a = it - 1;
}
void searchStr(char* str, char* Sstr)
{
int k = 0;
int it;
for (it = 1; str[it] != '\n'; ++it)
{
while (k > 0 && str[it] != Sstr[k+1])
k = automat[k];
if (Sstr[k+1] == str[it])
++k;
if (k == a)
{
if (b++ < 1000)
res.push(it - a);
}
}
}
int main()
{
FILE * fin = fopen("strmatch.in", "r");
FILE * fout = fopen("strmatch.out", "w");
fgets(A+1, 2000002, fin);
fgets(B+1, 2000002, fin);
buildKMP(A);
searchStr(B, A);// search A in B
fprintf(fout, "%d\n", b);
while (!res.empty())
{
fprintf(fout, "%d ", res.front());
res.pop();
}
fprintf(fout, "\n");
fclose(fin);
fclose(fout);
return 0;
}