Pagini recente » Cod sursa (job #2909899) | Cod sursa (job #685734) | Cod sursa (job #1193796) | Cod sursa (job #3239863) | Cod sursa (job #1813861)
#include<fstream>
#include<cstring>
#define DIM 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m, P[DIM], nr, sol[1005], L;
char a[DIM], b[DIM];
int main(){
fin >> a + 1;
fin >> b + 1;
n = strlen( a + 1 );
m = strlen( b + 1 );
//P[i] = lungimea celei mai lungi subsecventa a subsecventei 1...i care e prefix si sufix pentru ea
// astefel incat prefixul si sufixul sa fie disjuncte
L = 0;
P[1] = 0;
for( int i = 2; i <= n; i++ ){
while( L != 0 && a[i] != a[L + 1] ){
L = P[L];
}
if( a[i] == a[L + 1] ){
L++;
}
P[i] = L;
}
L = 0;
for( int i = 1; i <= m; i++ ){
while( L != 0 && b[i] != a[L + 1] ){
L = P[L];
}
if( b[i] == a[ L + 1] ){
L++;
}
if( L == n ){
L = P[L];
nr++;
if( nr <= 1000 ){
sol[nr] = i - n;
}
}
}
fout << nr << "\n";
for( int i = 1; i <= min(nr, 1000); i++ ){
fout << sol[i] << " ";
}
return 0;
}