Pagini recente » Cod sursa (job #2300348) | Cod sursa (job #1147182) | Cod sursa (job #2416773) | Cod sursa (job #950704) | Cod sursa (job #867541)
Cod sursa(job #867541)
#include<fstream>
#include<cstring>
using namespace std;
#define MAXN 2000001
char s1[MAXN], s2[MAXN];
int pi[MAXN], p[1024];
void calcul_prefix(int n){
int k = 0;
pi[1] = 0;
for ( int i = 2; i < n; i++){ // not sure about i <= n
while ( k > 0 && s1[k+1] != s1[i]){
k = pi[k];
}
if ( s1[k + 1] == s1[i] ){
k++;
}
pi[i] = k;
}
}
int potrivire(int n, int m){
int q = 0, t = 0;
for ( int i = 1; i < m; i++){
while( q > 0 && s1[q+1] != s2[i]){
q = pi[q];
}
if ( s1[q + 1] == s2[i]){
q++;
}
if ( q == n-1 ){
p[t++] = i-n+1;
}
}
return t;
}
int main(){
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int t,i;
fin.getline(s1, MAXN);
fin.getline(s2, MAXN);
calcul_prefix(strlen(s1));
t = potrivire(strlen(s1), strlen(s2));
fout << t << "\n";
for(i = 0; i < t; i++){
fout << p[i];
}
fin.close();
fout.close();
return 0;
}