Cod sursa(job #1073587)

Utilizator RobertSSamoilescu Robert RobertS Data 6 ianuarie 2014 16:33:17
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<string.h>
using namespace std;
 
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
 
 
#define MAX_N 2000001
int n, m;
char s1[MAX_N], s2[MAX_N];
 
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){
        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();
     
     
	int rez =  list.size();
    fout << rez << '\n';
	if(rez < 1000)
		for(size_t i = 0; i<list.size(); i++){
        fout << list[i] << " ";
		}
	else 
		for(size_t i = 0; i<1001; i++){
        fout << list[i] << " ";
		}
	
return 0;
}