Pagini recente » Cod sursa (job #2730350) | Cod sursa (job #2266018) | Cod sursa (job #2166159) | Cod sursa (job #1836692) | Cod sursa (job #1618655)
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
vector <int> Sol;
int L[100005];
int n, m;
char A[100005], B[100005], Aux[100005];
void citire()
{
f.getline(Aux, 100000);
A[0] = '*';
strcat(A, Aux);
f.getline(Aux, 100000);
B[0] = '*';
strcat(B, Aux);
n = strlen(A);
m = strlen(B);
}
void precalc()
{
int prev, i;
for(i=2; i<n; i++){
prev = L[i-1];
while(prev && A[i] != A[prev + 1])
prev = L[prev];
if(A[i] == A[prev + 1])
L[i] = prev + 1;
}
}
void KMP()
{
int potri = 0, i;
for(i=1; i<m; i++){
while(potri && B[i] != A[potri + 1]){
potri = L[potri];
}
if(B[i] == A[potri + 1])
potri++;
if(potri == (n-1))
Sol.push_back(i - n + 1);
}
g<<Sol.size()<<"\n";
for(i=0; i<Sol.size() && i<1000; i++)
g<<Sol[i]<<" ";
}
int main()
{
citire();
precalc();
KMP();
return 0;
}