Pagini recente » Cod sursa (job #109197) | Cod sursa (job #813405) | Cod sursa (job #2269327) | Cod sursa (job #890158) | Cod sursa (job #2905448)
// KMP algorithm
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int MAXN = 2e6;
ifstream fin( "strmatch.in" );
ofstream fout( "strmatch.out" );
vector <int> poz;
int longestPrefixSuffix[MAXN];
int main() {
int i, j, lenmax;
string str, pattern;
fin >> pattern >> str;
longestPrefixSuffix[0] = 0;
for( i = 1; i < pattern.size(); i++ ) {
lenmax = longestPrefixSuffix[i-1];
while( lenmax && pattern[i] != pattern[lenmax] )
lenmax = longestPrefixSuffix[lenmax-1];
if( pattern[i] == pattern[lenmax] )
longestPrefixSuffix[i] = lenmax + 1;
}
//for( i = 0; i < pattern.size(); i++ )
// cout << longestPrefixSuffix[i] << " ";
i = j = 0;
while( i < str.size() ) {
if( str[i] == pattern[j] ) {
i++, j++;
if( j == pattern.size() ) {
poz.push_back( i - j );
j = longestPrefixSuffix[j - 1];
}
}
else {
if( j > 0 )
j = longestPrefixSuffix[j - 1];
else
i++;
}
}
fout << poz.size() << "\n";
for( auto it: poz )
fout << it << " ";
return 0;
}