Pagini recente » Cod sursa (job #547232) | Cod sursa (job #1589858) | Cod sursa (job #2737526) | Cod sursa (job #1147469) | Cod sursa (job #1618678)
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
vector <long long> Sol;
long long L[2000005];
long long n, m;
char A[2000005], B[2000005], Aux[2000005];
void citire()
{
f.getline(Aux, 2000005);
A[0] = '*';
strcat(A, Aux);
f.getline(Aux, 2000005);
B[0] = '*';
strcat(B, Aux);
n = strlen(A);
m = strlen(B);
}
void precalc()
{
long long 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()
{
long long 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]<<" ";
g<<"\n";
}
int main()
{
citire();
precalc();
KMP();
return 0;
}