Pagini recente » Cod sursa (job #2928477) | Cod sursa (job #2533860) | Cod sursa (job #1333394) | Cod sursa (job #2220668) | Cod sursa (job #2439154)
#include <bits/stdc++.h>
#define NMAX 2000000
using namespace std;
int lps[NMAX + 1];
vector<int> ans;
string source, pat;
void build_lps( int n ) {
int len, i;
len = 0;
i = 1;
lps[0] = 0;
while( i < n ) {
if( pat[len] == pat[i] ) {
len ++;
lps[i] = len;
i ++;
}
else {
if( len != 0 )
len = lps[len - 1];
else
lps[i] = len, i ++;
}
}
}
void kmp( int n, int m ) {
int i, j;
i = 0;
j = 0;
while( i < m ) {
if( pat[j] == source[i] ) {
i ++;
j ++;
}
if( j == n ) {
ans.push_back(i - j);
j = lps[j - 1];
}
else if( i < m && pat[j] != source[i] ) {
if( j != 0 )
j = lps[j - 1];
else
i ++;
}
}
}
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m, i, j;
fin>>pat;
fin>>source;
n = pat.size();
m = source.size();
build_lps(n);
kmp(n,m);
fout<<ans.size()<<"\n";
for( i = 0; i < min(1000,(int)ans.size()); i ++ )
fout<<ans[i]<<" ";
return 0;
}