Pagini recente » Cod sursa (job #906499) | Cod sursa (job #2409301) | Cod sursa (job #769674) | Cod sursa (job #1742660) | Cod sursa (job #2905480)
// Mihai Priboi
#include <bits/stdc++.h>
using namespace std;
#define MAXN 2000000
int prefix[MAXN];
char s[MAXN + 1], pattern[MAXN + 1];
int pSize, sSize;
void computePrefixes() {
int i, pLen;
prefix[0] = 0;
for( i = 1; i < pSize; i++ ) {
pLen = prefix[i - 1];
while( pLen && pattern[i] != pattern[pLen] )
pLen = prefix[pLen - 1];
if( pattern[i] == pattern[pLen] )
prefix[i] = pLen + 1;
}
}
int main() {
FILE *fin, *fout;
int i, j;
fin = fopen( "strmatch.in", "r" );
fscanf( fin, "%s\n%s", pattern, s );
fclose( fin );
pSize = strlen(pattern);
sSize = strlen(s);
computePrefixes();
vector<int> rez;
i = j = 0;
while( i < sSize ) {
if( s[i] == pattern[j] ) {
i++;
j++;
if( j == pSize ) {
rez.push_back(i - j);
j = prefix[j - 1];
}
}
else {
if( j > 0 )
j = prefix[j - 1];
else
i++;
}
}
fout = fopen( "strmatch.out", "w" );
fprintf( fout, "%d\n", rez.size() );
for( i = 0; i < rez.size() && i < 1000; i++ )
fprintf( fout, "%d ", rez[i] );
fclose( fout );
return 0;
}