Cod sursa(job #1069939)

Utilizator RobertSSamoilescu Robert RobertS Data 30 decembrie 2013 18:30:04
Problema Potrivirea sirurilor Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<string.h>
using namespace std;
 
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
 
 
#define MAX_N 200001
int n, m;
char* s1, *s2;
 
void read(){
    char f1[MAX_N], f2[MAX_N];
    fin.get(f1,MAX_N);
    fin.get();
    fin.get(f2,MAX_N);
     
	
	s1 = new char();
	s2 = new char();
    strcat(s1,"x");
	strcat(s2,"x");
     
     
    strcat(s1,f2);
    strcat(s2,f1);
    m = strlen(s2)-1;
    n = strlen(s1)-1;
	
 
}
 
 
int ol[MAX_N];
 
vector<int>list;
 
 
void overLap(){
    for(int k=1; k<m; k++){
        char c = s2[k+1];
        int v = ol[k];
        while(s2[v+1] !=c && v!=0){
            v = ol[v];
        }
        if(s2[v+1] == c)
            ol[k+1] = v+1;
        else
            ol[k+1] = 0;
    }
}
 
 
 
void solve(){
    int i=1, j=1, k=1;
    while(n-k >= m-1){
        while(j <=m && s1[i] == s2[j]){
            i++,  j++;
        }
         
        if(j > m) list.push_back(k-1);
        if(ol[j-1] > 0){
            k = i - ol[j-1];
        }else{
            if(i==k) i++;
            k = i;
        }
        if(j > 1) j= ol[j-1]+1;
    }
 
     
     
}
 
int main(){
    read();
    overLap();
    solve();
     
     
    fout << list.size() << endl;
    for(size_t i = 0; i<list.size(); i++){
        fout << list[i] << " ";
    }
	
	
return 0;
}