Pagini recente » Cod sursa (job #1072110) | Cod sursa (job #805283) | Cod sursa (job #1306796) | Cod sursa (job #2776773) | Cod sursa (job #2461577)
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <cstring>
using namespace std;
//#include <iostream>
#include <fstream>
//ifstream cin ("input.in");
//ofstream cout ("output.out");
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
static const int NMAX = 2e6+5;
char s[2*NMAX];
int kmp[2*NMAX];
vector <int> v;
int solve( int n, int targetLen) {
int ans = 0;
for ( int i = 2; i <= n; ++i ) {
kmp[i] = kmp[i-1];
while ( kmp[i] && s[kmp[i]+1] != s[i] ) {
kmp[i] = kmp[kmp[i]];
}
if ( s[kmp[i]+1] == s[i] ) {
kmp[i]++;
}
if ( kmp[i] == targetLen ) {
ans++;
if ( ans > 1000 ) {
continue;
}
v.push_back(i-2*kmp[i]-1);
}
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>(s+1);
int n = strlen(s+1);
s[n+1] = '#';
cin>>(s+n+2);
int k = strlen(s+1);
cout<<solve(k, n)<<'\n';
for ( auto x:v ) {
cout<<x<<" ";
}
}