Pagini recente » Cod sursa (job #2744821) | Cod sursa (job #2743597) | Cod sursa (job #1452621) | Cod sursa (job #2798174) | Cod sursa (job #2530736)
#include <bits/stdc++.h>
#define MAX 2000025
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int n, m,cnt, pi[MAX] , z, v[1001];
char s1[MAX], s2[MAX];
int main(){
in.getline(s1, MAX);
in.getline(s2, MAX);
n = strlen(s1);
m = strlen(s2);
for(int i = n; i >= 1; i--)
s1[i] = s1[i-1];
for(int j = m; j >= 1; j--)
s2[j] = s2[j - 1];
s1[0] = s2[0] = ' ';
int k = 0;
pi[1] = 0;
for(int i = 2; i <= n; i++){
while(k > 0 && s1[i] != s1[k + 1])
k = pi[k];
if(s1[k + 1] == s1[i]) k++;
pi[i] = k;
}
k = 0;
for(int i = 1; i <= m; i++){
while(k > 0 && s1[k+1] != s2[i])
k = pi[k];
if(s1[k + 1] == s2[i])
k++;
if(k == n && z <= 1000) v[++z] = i - n;
}
out<<z<<"\n";
for(int i = 1; i <= z; i++)
out<<v[i]<<" ";
}