Pagini recente » Cod sursa (job #1114381) | Cod sursa (job #2442907) | Borderou de evaluare (job #1567317) | Cod sursa (job #699834) | Cod sursa (job #1254627)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <string.h>
using namespace std;
const int Nmax = 2000666;
string A, B;
int T[Nmax];
vector<int> sol;
void preprocess(string &A)
{
int N = A.length();
T[0] = -1;
T[1] = 0;
for(int i = 2; i <= N; i++)
{
int j = i-1;
while(T[j] > -1)
{
if (A[i-1] == A[T[j]]) {
T[i] = T[j] + 1;
break;
} else {
j = T[j];
}
}
}
}
int main()
{
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
f >> A >> B;
int N = A.length();
int M = B.length();
preprocess(A);
int m = 0, i = 0;
while(m+N <= M) {
if (B[m+i] == A[i])
{
i++;
if (i == N)
{
sol.push_back(m);
int j = T[i];
m += i - j;
i = j > 0 ? j : 0;
}
}
else
{
int j = T[i];
m += i - j;
i = j > 0 ? j : 0;
}
}
g << sol.size() << '\n';
for (size_t i = 0; i < 1000 && i < sol.size(); i++)
g << sol[i] << ' ';
g << '\n';
return 0;
}