Pagini recente » Cod sursa (job #854206) | Cod sursa (job #302058) | Cod sursa (job #1664643) | Cod sursa (job #168924) | Cod sursa (job #2173976)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[100005], B[100005];
int P[100005], N, M;
vector <int> Sol;
void pref()
{
int q = 0;
P[1] = 0;
for(int i = 2; i <= N; i++)
{
while(q && A[i] != A[q + 1])
q = P[q];
if(A[i] == A[q + 1])
q++;
P[i] = q;
}
}
void Solve()
{
int q = 0, nb = 0;
for(int i = 1; i <= M; i++)
{
while(q && B[i] != A[q + 1])
q = P[q];
if(B[i] == A[q + 1])
q++;
if(q == N)
{
nb++;
if(nb <= 1000)
Sol.push_back(i - N);
}
}
g << nb << "\n";
for(int i = 0; i < Sol.size(); i++)
{
g << Sol[i] << " ";
}
g << "\n";
}
int main()
{
f.getline(A + 1, 100005);
f.getline(B + 1, 100005);
N = strlen(A + 1);
M = strlen(B + 1);
pref();
Solve();
return 0;
}